Bir öğedeki tepe öğesi c

Question

Bir dizi tamsayı veriyorum. İçinde tepe noktası bulmak zorundayım. Bir dizi öğesi, komşularına göre daha küçük değil DEĞİL. Köşe elemanları için sadece bir komşu göz önünde bulundurun. Örneğin

:

girdi dizisinin {10, 20, 15, 2, 23, 90, 67} için iki tavan elemanları vardır: 20 ve herhangi bir tek tepe elemanı dönmek gerekir 90..

Denediğim çözüm, bir dizi doğrusal taramadır ve bir tepe öğesi buldum. Bu yöntemin en kötü durum zaman karmaşıklığı O (n) olacaktır.

En yüksek elementi en kötü zaman karmaşıklığında O (n) 'den daha iyi bulabilir miyiz?

Answer 1

Evet, ikili aramaya benzer bir fikir kullanarak O (log n) içinde yapabilirsiniz. Vektörün ortasına gelin ve komşularını kontrol edin. Komşularının her ikisinden de daha büyükse, o zaman öğeyi döndürün, bu bir tepe noktasıdır. Doğru eleman daha büyükse, dizinin sağ tarafında yinelemeli olarak zirveyi bulun. Sol eleman daha büyükse, dizinin sol tarafında yinelemeli olarak zirveyi bulun.

Answer 2

Evet, daha iyi bir zaman karmaşıklığında bulmak mümkündür. Devide ve yöntem kullanarak

Aşağıdaki bağlantı size yardımcı olacaktır. http://courses.csail.mit.edu/6.006/spring11/lectures/lec02.pdf

Answer 3

diğer halklar cevapları gereğince (benim aşağıda) bazı kod (O ile() n günlük):

// A divide and conquer solution to find a peak element element 
#include <stdio.h> 

// A binary search based function that returns index of a peak element 
int findPeakUtil(int arr[], int low, int high, int n) 
{ 
    // Fin index of middle element 
    int mid = low + (high - low)/2; /* (low + high)/2 */ 

    // Compare middle element with its neighbours (if neighbours exist) 
    if ((mid == 0 || arr[mid-1] <= arr[mid]) && 
      (mid == n-1 || arr[mid+1] <= arr[mid])) 
     return mid; 

    // If middle element is not peak and its left neighbor is greater than it 
    // then left half must have a peak element 
    else if (mid > 0 && arr[mid-1] > arr[mid]) 
     return findPeakUtil(arr, low, (mid -1), n); 

    // If middle element is not peak and its right neighbor is greater than it 
    // then right half must have a peak element 
    else return findPeakUtil(arr, (mid + 1), high, n); 
} 

// A wrapper over recursive function findPeakUtil() 
int findPeak(int arr[], int n) 
{ 
    return findPeakUtil(arr, 0, n-1, n); 
} 

/* Driver program to check above functions */ 
int main() 
{ 
    int arr[] = {1, 3, 20, 4, 1, 0}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
    printf("Index of a peak point is %d", findPeak(arr, n)); 
    return 0; 
} 

olmak yanı

o kontrol edebilir MİT 6,006 OCW kursu için bu Kullanılmış

http://courses.csail.mit.edu/6.006/spring11/rec/rec02.pdf