Какова большая сложность этого алгоритма?

Question

У меня есть функция, которую я написал ниже. Эта функция по существу является сортировкой слияния.

public static long nlgn(double[] nums) { 

     if(nums.length > 1)  { 
      int elementsInA1 = nums.length/2; 
      int elementsInA2 = nums.length - elementsInA1; 
      double[] arr1 = new double[elementsInA1]; 
      double[] arr2 = new double[elementsInA2]; 

      for(int i = 0; i < elementsInA1; i++) 
      arr1[i] = nums[i]; 

      for(int i = elementsInA1; i < elementsInA1 + elementsInA2; i++) 
      arr2[i - elementsInA1] = nums[i]; 

      nlgn(arr1); 
      nlgn(arr2); 

      int i = 0, j = 0, k = 0; 

      while(arr1.length != j && arr2.length != k) { 
       if(arr1[j] <= arr2[k]) { 
        nums[i] = arr1[j]; 
        i++; 
        j++; 
       } else { 
        nums[i] = arr2[k]; 
        i++; 
        k++; 
       } 
      } 

      while(arr1.length != j) { 
       nums[i] = arr1[j]; 
       i++; 
       j++; 
      } 
      while(arr2.length != k) { 
       nums[i] = arr2[k]; 
       i++; 
       k++; 
      } 
     } 

     return nuts; 
    } 

Поскольку это сортировка слиянием, я знаю из моих исследований, что сложность большой-O этого алгоритма O (п ЛГН). Однако, когда я запускаю свои тесты времени, полученные результаты не предполагают, что это работает в O (n lgn) времени. Кажется, что это O (n lgn) время, хотя, потому что до тех пор, пока мы не дойдем до конца двух циклов в начале. он работает в O (n) времени. После этого он должен работать в O (lgn), поскольку он сортирует каждый элемент.

Мой вопрос: может ли кто-нибудь подтвердить, что этот кусок кода работает в O (n lgn) раз? Если нет, я хотел бы знать, где я ошибаюсь в своем понимании.

Answer 1

Поскольку это сортировка слиянием, я знаю из моих исследований, что сложность большой-O этого алгоритма O(n lgn). [...] Мой вопрос в том, может ли кто-нибудь подтвердить, что этот фрагмент кода работает в O(n lgn) времени?

Нет необходимости, чтобы показать это, потому что сортировка слиянием уже доказано работать в O(n lg(n)) времени. Но если вы хотите это наблюдать, вам нужно поэкспериментировать со все большими значениями для ваших входов. Возможно, вам захочется обновить сообщение с вашими входными значениями и результатами синхронизации.

Однако, когда я запускаю свои тесты времени, результаты, полученные мной, не предполагают, что это работает в O(n lgn) времени. [...] Если нет, я хотел бы знать, где я ошибаюсь в своем понимании.

Я думаю, что вы можете не понимать, что нотация Big-Oh действительно пытается вам сказать. Big-O дает вам асимптотического алгоритма алгоритма, так как входы становятся достаточно большими. (Как «большой» «достаточно большой» будет варьироваться от алгоритма к алгоритму и должен быть найден путем экспериментов. Дело в том, что это значение делает , и мы представляем его более абстрактно.)

Иными словами , Big-O говорит вам, что худшее дело производительность алгоритма может быть как N становится очень большим. Поскольку это наихудший сценарий, это также означает, что при некоторых обстоятельствах он может работать лучше, но мы, как правило, не заботимся об этом. (Посмотрите на Big-Omega и Big-Theta, если вам интересно.) Например, если у вас есть список с достаточно маленьким числом, сортировка merge может работать быстрее, чем quick-sort, и это часто используется в качестве оптимизации.

Это также приближение, потому что константы и другие полиномиальные члены - это , а не, обозначенные как часть обозначений.Например, некоторый гипотетический алгоритм с временной сложностью 500x^2 + 15x + 9000 будет записан как O(n^2).

Некоторые причины падения младшие члены включают в себя:

• Относительная Размер: Как n стремится к положительной бесконечности, тем больше n^2 термин доминирует; нижние условия вносят все меньше и меньше в общую стоимость по сравнению с самым большим/доминирующим термином - например, добавляя несколько капель или ведер воды в озеро;
• Удобство: Чтение и понимание O(n^2) проще, чем длинный и более сложный полиномом никакой реальной пользы

Answer 2

O (nlogn) - асимптотически плотная граница. Это означает, что только когда n достаточно велико, его время работы близко к сложности. Когда n мало, из-за служебного вызова функции и многих других факторов, граница не является жесткой.

Вы можете сделать n больше и сравнить отношения между входами, чтобы увидеть, близко ли он к O (nlogn). Хотя я очень сомневаюсь, насколько велика вы должны сделать п быть ...