Как найти точную сложность времени и сложность пространства для ниже новых алгоритмов быстрой сортировки

Question

Я создал новый алгоритм сортировки. Основная концепция этого алгоритма - найти самый маленький и самый большой элемент из данного списка и поменять их на левый угол и правый угол элементов, это будет повторяться до тех пор, пока мы не достигнем среднего элемента.

Этот алгоритм выполняется за очень короткое время, чем Quick sort и merge sort. Я хочу убедиться, что этот алгоритм работает лучше, чем Quick sort.

Мой алгоритм код

public class VeryQuickVersion1 
{ 

    public static void main(String args[]) 
    { 

     long current = System.nanoTime(); 

     int[] first = { 8 ,1 ,3 ,2, 6, 5, 7, 4, 12 ,9, 11 ,10 ,14 ,13, 15}; 

     for (int x=0,y=first.length - 1;x<y;x++,y--) 
     { 
      int low = 0; 
      int high = 0; 
      int li = 0; 
      int hi = 0; 
      for (int i = x; i <= y; i++) 
      { 
       if (i == x) 
       { 
        low = first[i]; 
        high = first[i]; 
       } 
       if (low > first[i]) 
       { 
        low = first[i]; 
        li = i; 
       } 
       if (high < first[i]) 
       { 
        high = first[i]; 
        hi = i; 
       } 
      } 

      first[li]=first[x]; 
      first[hi]=first[y]; 

      first[x]=low; 
      first[y]=high; 
     } 
    /* for(int i:first){ 
      System.out.println(i); 
     }*/ 
     System.out.println(System.nanoTime() - current); 
    } 
} 

время, затрачиваемое этого алгоритма: 10148 и время, затрачиваемое алгоритмом быстрой сортировки для того же списка: 17498

Answer 1

сложность времени для приведенного выше алгоритма, кажется O(n^2).

Как видите, есть 2 вложенных петли for. внешний - от x = 0, y = n до x < y, и на каждом этапе он уменьшает x++ и y--. В то время как другая внутренняя петля идет от x до y.

Это можно увидеть как серию n + (n-2) + (n-4) + .... + 0. Что ясно дает временную сложность O(n^2)

---

Временная сложность не рассчитывается так, как вы делаете. Вы должны проверить, как время, затрачиваемое этой программой, будет увеличиваться при увеличении размера ввода. И проверьте то же самое с различными типами входов, (например, по возрастанию, случайным и т. Д.).

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

---

ПРИМЕЧАНИЕ: Вы можете увидеть реальную разницу, как время, затраченное на повышение this сайте. Обратите внимание, как время увеличивается после увеличения длины ввода до 50000.

Answer 2

Вы не установить ориентиры на любой алгоритм с таким небольшим размером данных. Размер вашего массива равен 10, что на самом деле является небольшим размером.

Создайте массив размером ~ 10^5 или 10^6, а затем проверьте производительность.

Кроме того, просто взглянув на код, я могу сказать, что этот алгоритм хуже, чем Quick Sort. В асимптотической сложности быстрый вид - O (n log n), тогда как это ясно O (n^2).

Я использовал Arrayys.sort для сортировки массива с помощью быстрого сортировки.

Вот результаты:

массив размером 1000

For Quick Sort algorithm: 
1817634 

For my algorithm: 
8105038 

массив размером 100000

For Quick Sort algorithm: 
21210010 

For my algorithm: 
7117304154 

Вы можете ясно увидеть разницу.

Мой код, просто для справки: (Для моего алгоритма, я просто скопировал код)

import java.util.*; 

public class Quick{ 

public static void main(String args[]) { 


    Scanner in = new Scanner(System.in); 
    int n = in.nextInt(); 

    int[] first = new int[n]; 
    for(int i = 0; i < n; i++){ 
     first[i] = in.nextInt(); 
    } 

    int second[] = first.clone(); 

    long current = System.nanoTime(); 
    Arrays.sort(second); 
    System.out.println("For Quick Sort algorithm:\n" + (System.nanoTime() - current) + "\n"); 

    current = System.nanoTime(); 

    for (int x=0,y=first.length - 1;x<y;x++,y--) { 
     int low = 0; 
     int high = 0; 
     int li = 0; 
     int hi = 0; 
     for (int i = x; i <= y; i++) { 
      if (i == x) { 
       low = first[i]; 
       high = first[i]; 
      } 
      if (low > first[i]) { 
       low = first[i]; 
       li = i; 
      } 
      if (high < first[i]) { 
       high = first[i]; 
       hi = i; 
      } 
     } 

     first[li]=first[x]; 
     first[hi]=first[y]; 

     first[x]=low; 
     first[y]=high; 
    } 
/* for(int i:first){ 
     System.out.println(i); 
    }*/ 
    System.out.println("For my algorithm:\n" + (System.nanoTime() - current)); 



} 
}