Помогите проверить Big O

Question

Привет, поэтому я пытаюсь проверить некоторые алгоритмы сортировки.

• Вставка сортировки

• Слияние

• Быстрая сортировка с использованием разбиения «медиана трех» и отсечение 10 (с использованием сортировки вставкой для небольших частей массива)

Анализ:
Время выполнения в наихудшем случае дляСортировка вставки обсуждалась как O (n ² ), с фактическим временем выполнения O (n) для отсортированного ввода (при условии, что внутренний цикл правильно закодирован).Было рассмотрено, что Mergesort будет O (n log n) для всех входных данных.Быстрая сортировка, использующая разбиение «медиана трех» и разумное ограничение, обсуждалась как O (n Log (n)) для всех входных данных, но на практике быстрее, чем Mergesort.Проверяют ли ваши тайминги эти вычисления?

обратите внимание, что N = Max / 2 и 2N = MAX

После запуска программ я обнаружил, что

The diff for insertion sorted with sorted max/2 is 0.000307083129882812
The diff for insertion sorted with sorted max is 0.000623941421508789
The diff for insertion reverse with sorted max/2 is 0.000306129455566406
The diff for insertion reverse with sorted max is 0.000745058059692383
The diff for insertion random with sorted max/2 is 2.39158606529236
The diff for insertion random with sorted max is 9.72073698043823
The diff for merge sort with sorted max/2 is 0.00736188888549805
The diff for merge sort with sorted max is 0.0154471397399902
The diff for merge reverse with sorted max/2 is 0.00730609893798828
The diff for merge reverse with sorted max is 0.0154309272766113
The diff for merge random with sorted max/2 is 0.0109999179840088
The diff for merge random with sorted max is 0.0232758522033691
The diff for quick sorted with sorted max/2 is 3.10367894172668
The diff for quick sorted with sorted max is 12.5512340068817
The diff for quick reverse with sorted max/2 is 3.09689497947693
The diff for quick reverse with sorted max is 12.5547797679901
The diff for quick random with sorted max/2 is 0.0112619400024414
The diff for quick random with sorted max is 0.0221798419952393

Я знаючто сортировка вставки работает правильно, так как для случайного, я сделал 9.72073698043823 / 2.39158606529236 ~ = 4 = 2 ² = O (n ² )

, но я надеваюне знаю, как проверить, являются ли другие O (n Log (n)) или нет.Пожалуйста, помогите

Answer 1

Позвольте мне напомнить вам, что f (n) = O (n) означает предел, когда n становится очень большим, что f (n) / n => постоянная

Что не сказано:

• эта константа может быть очень большой
• что для малых значений это что-то значит, например: 10 ^ 9 / n + n равно O (n), но для n = 1 оно равно 10 ^ 9 + 1; -)
• O (что-то) не является убийцей аргументов, топология ваших данных может когда-нибудь повлиять на алгоритм (например, на «почти» отсортированных данных, пузырьковая сортировка работает хорошо)

Если вы хотите сделать выводы, запустите тестирование с большими образцами, релевантными для вашего приложения, не делайте вывод слишком рано (учтите, что современный ЦП может обмануть вас кешем, конвейерной обработкой и многоядерностью, если вы его используете (что вы можете сделать для сортировка)