Вставка Сортировка Средний случай, дающий n вместо n^2, если только в действительно больших размерах массива

im, имеющих проблему со средним случаем сортировки вставки и тестирования/реализации.Вставка Сортировка Средний случай, дающий n вместо n^2, если только в действительно больших размерах массива

Насколько я знаю, это означало быть n^2, и когда я делал от 1 до 200000 массивов, заполненных случайными числами, я получил именно это. Но теперь, когда я делаю 20 баллов и вычисляю среднее значение для обеспечения этого, я получаю прямую линию, поэтому O (n)

Однако, когда я пробовал массивы размером 100 000, от 100 000 до 1 000 000, я получаю несколько изогнутую квадратичную линию

public static void averageCase() { 
    for (int x = 10000; x <= 30000; x += 1000) { 
     int[] averageArray = randomArray(x); 
     float average = 0; 
     for (int i = 1; i <= 100000; i++) { 
      float startTime = System.nanoTime(); 
      insertionSort(averageArray, averageArray.length); 
      float estimateTime = System.nanoTime() - startTime; 
      average += estimateTime; 
     } 
     System.out.println(average/100000); 
    } 
} 

public static int[] randomArray(int n) { 
    Random random = new Random(); 
    int[] randomArray = new int[n]; 
    for (int i = 0; i < randomArray.length; i++) { 
     randomArray[i] = random.nextInt(1000); 
    } 
    return randomArray; 
}

результаты:

16504,586

18559,795

20468,203

22083,01

23530,045

25186,795

27179,09

28793,896

30534,533

32149,34

33869.004

35819,355

37539,02

39216,742

40978,35

42551,215

44186,992

46158,316

47584,38

49660,56

51191,48

источник

2017-02-11 mcgee111

Да, и?O (n^2) относится к долгосрочному поведению, он может выглядеть по-разному при малых n. –

Согласиться с Луи, О, тета и омега время только ссылаются на асимптотические границы. Попробуйте с входами гораздо ближе к бесконечности. А затем исключить все возможные проблемы с тестированием во время выполнения, такие как скрытое поведение, такое как кеширование, а также все остальное, что делает физические компьютеры отличными от теоретических. И тогда вы можете увидеть результаты, соответствующие вашим ожиданиям. – CollinD

Я просто убедился, что, честно говоря, я потратил столько времени, думая, что что-то не так с моим методом реализации, потому что я уже опробовал и подтвердил лучший и худший случай, и не был уверен, почему я не смог получить соответствующие измерения. – mcgee111

Запомнить O (N^2) сигналов верхней границы. Сортировка вставки имеет линейную нижнюю границу. Попробуйте с большими числами и кучей раз.

источник

2017-02-11 00:35:28

В вашем внутреннем цикле вы неоднократно сортируете один и тот же массив, а не производите его каждый раз.

for (int i = 1; i <= 100000; i++) { 
    float startTime = System.nanoTime(); 
    insertionSort(averageArray, averageArray.length); 
    float estimateTime = System.nanoTime() - startTime; 
    average += estimateTime; 
}

Поскольку сортировка вставкой работает в линейном времени на уже отсортированного ввода, вы измеряете 1/100000 алгоритма квадратичного времени и 99999/100000 линейного алгоритма времени.

И поэтому ваши тайминги гораздо более плоские, чем вы ожидаете.

источник

2017-02-11 15:10:08

Вставка Сортировка Средний случай, дающий n вместо n^2, если только в действительно больших размерах массива

ответ

Смежные вопросы