違反在大O符號給定的平均時間複雜度

Question

我想實現一個解決方案，以找到第k大元素與那些在大O符號O(N*log(N))平均時間複雜度，其中N是重複一個給定的整數列表列表中的元素數量。

按我的理解合併排序具有但是在我下面的代碼，我實際使用一個額外的for循環與歸併算法一起刪除重複這肯定是侵犯了我的發現規則第k大的O(N*log(N))的平均時間複雜度元素與O(N*log(N))。我如何通過完成我的任務O(N*log(N)) Big-O表示法的平均時間複雜性？這裏

public class FindLargest { 
    public static void nthLargeNumber(int[] arr, String nthElement) { 
     mergeSort_srt(arr, 0, arr.length - 1); 
     // remove duplicate elements logic 
     int b = 0; 
     for (int i = 1; i < arr.length; i++) { 
      if (arr[b] != arr[i]) { 
       b++; 
       arr[b] = arr[i]; 
      } 
     } 

     int bbb = Integer.parseInt(nthElement) - 1; 
     // printing second highest number among given list 
     System.out.println("Second highest number is::" + arr[b - bbb]); 
    } 

    public static void mergeSort_srt(int array[], int lo, int n) { 
     int low = lo; 
     int high = n; 
     if (low >= high) { 
      return; 
     } 

     int middle = (low + high)/2; 
     mergeSort_srt(array, low, middle); 
     mergeSort_srt(array, middle + 1, high); 
     int end_low = middle; 
     int start_high = middle + 1; 
     while ((lo <= end_low) && (start_high <= high)) { 
      if (array[low] < array[start_high]) { 
       low++; 
      } else { 
       int Temp = array[start_high]; 
       for (int k = start_high - 1; k >= low; k--) { 
        array[k + 1] = array[k]; 
       } 
       array[low] = Temp; 
       low++; 
       end_low++; 
       start_high++; 
      } 
     } 
    } 

    public static void main(String... str) { 
     String nthElement = "2"; 
     int[] intArray = { 1, 9, 5, 7, 2, 5 }; 

     FindLargest.nthLargeNumber(intArray, nthElement); 
    } 
} 

Answer 1

問題是你的合併程序，你必須使用另一種循環，我DONOT明白爲什麼，所以我會說你的合併爲O（n^2）改變你的合併排序時間至O的算法（N^2）。

這裏是典型的O（N）的僞代碼合併程序： -

void merge(int low,int high,int arr[]) { 


    int buff[high-low+1]; 
    int i = low; 
    int mid = (low+high)/2; 
    int j = mid +1; 
    int k = 0; 
    while(i<=mid && j<=high) { 

     if(arr[i]<arr[j]) { 
      buff[k++] = arr[i]; 
      i++; 
     } 
     else { 
      buff[k++] = arr[j]; 
      j++; 
     } 
    } 

    while(i<=mid) { 
     buff[k++] = arr[i]; 
      i++;  
    } 

    while(j<=high) { 
     buff[k++] = arr[j]; 
      j++;  
    } 


    for(int x=0;x<k;x++) { 

     arr[low+x] = buff[x]; 
    } 

} 

Answer 2

你只有在這裏的問題是，你不知道該怎麼辦的時候分析。如果您有一個需要O（n）的例程和一個採用O（n * log（n））的例程，則兩者都運行總共需要O（n * log（n））。因此，您的代碼像O（n * log（n））那樣運行。當且僅當存在值c> 0和y時，我們纔會注意到O（）的定義如下： f（x）∈O（g（x））當x> y時，f（x）< cg（x）。

您的合併排序在O（n * log（n））中，它告訴我們當某個c1，y1的n> y1時，它的運行時間以c1 * n * log（n）爲界。您的重複消除在O（n）中，告訴我們，當某個c2和y2的n> y2時，其運行時間受c2 * n約束。利用這一點，我們可以知道，兩者的總運行時間由C1 * N *的log（n）+ C2 * N N時> MAX（Y1，Y2）上界。我們知道，C1 * N *的log（n）+ C2 * N < C1 * N *的log（n）+ C2 * N *的log（n），因爲的log（n）> 1，這當然簡化爲（C1 + C2）* N *的log（n）。因此，我們可以知道兩個一起的運行時間由（C1 + C2）* N *的log（n）當n> MAX（Y1，Y2），並且因此，使用C1 + C2作爲我們的c和最大上界（y1，y2）作爲我們的y，我們知道兩者的運行時間在O（n * log（n））中。如果一段代碼是O（n），第二段代碼是O（n^2），那麼組合是O（n^2），因此非正式地，你可以知道更快的增長函數總是占主導地位。如果一個是O（log（n）），第二個是O（n），則組合是O（n）。如果一個是O（n^20），第二個是O（n^19.99），則組合是O（n^20）。如果一個是O（n^2000），第二個是O（2^n），那麼組合是O（2^n）。