, нарушающий заданную среднюю временную сложность в нотации Big-O

Question

Я пытаюсь реализовать решения для поиска k-го наибольшего элемента в заданном целочисленном списке с дубликатами с O(N*log(N)) средней сложности времени в нотации Big-O, где N - количество элементов в списке.

Согласно моему пониманию, Merge-sort имеет среднюю временную сложность O(N*log(N)), однако в моем нижнем коде я фактически использую дополнительный цикл for вместе с алгоритмом mergesort для удаления дубликатов, который определенно нарушает мое правило найти k-й самый большой элемент с 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), который изменяет время сортировки слияния О (п^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)), как вы хотите.

Чтобы сделать что-то формально, отметим, что определение O() состоит в следующем: f (x) ∈ O (g (x)) тогда и только тогда, когда существуют значения c> 0 и y такие, что f (x) < cg (x) всякий раз, когда x> y.

Ваш сортировка слияния находится в O (n * log (n)), который говорит нам, что его время работы ограничено сверху c1 * n * log (n), когда n> y1 для некоторого c1, y1. Вы устраняете дублирование в O (n), что говорит о том, что его время работы ограничено c2 * n при n> y2 для некоторых c2 и y2. Используя это, мы можем знать, что общее время работы этих двух ограничено сверху 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 + с2) * п * журнала (п). Таким образом, мы можем знать, что время работы двух вместе ограничено сверху (c1 + c2) * n * log (n) при n> max (y1, y2) и, таким образом, используя c1 + c2 в качестве наших c и max (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).