O (N log N) Сложность - Как и линейная?

Поэтому я думаю, что меня похоронят, чтобы задать такой тривиальный вопрос, но я немного смущен.

Я реализовал quicksort в Java и C, и я делал некоторые базовые сравнения. График выходил как две прямые линии, причем C был на 4 мс быстрее, чем Java-аналог более 100 000 случайных чисел.

Код моих тестов можно найти здесь;

андроид-тесты

Я не был уверен, что будет выглядеть строка (n log n), но я не думал, что это будет прямо. Я просто хотел проверить, что это ожидаемый результат, и что я не должен пытаться найти ошибку в моем коде.

Я вложил формулу в excel, а для основания 10 это кажется прямой линией с изломом в начале. Это потому, что разница между log (n) и log (n + 1) линейно возрастает?

Благодаря,

Гав

Ответ 1

Сделайте граф больше, и вы увидите, что O (n logn) не совсем прямая. Но да, это довольно близко к линейному поведению. Чтобы понять, почему, просто возьмите логарифм из нескольких очень больших чисел.

Например (база 10):

log(1000000) = 6
log(1000000000) = 9
…

Таким образом, для сортировки 1 000 000 номеров сортировка O (n logn) добавляет незначительный коэффициент 6 (или немного больше, поскольку большинство алгоритмов сортировки будут зависеть от логарифмов базы 2). Не очень много.

Фактически этот логарифмический фактор настолько необычайно мал, что на большинстве порядков установленные алгоритмы O (n logn) превосходят алгоритмы линейного времени. Важным примером является создание структуры данных массива суффикса.

Простой случай недавно укусил меня когда я попытался улучшить сортировку коротких строк quicksort, используя сортировку radix. Оказывается, для коротких строк это (линейное время) сортировка радикса было быстрее, чем quicksort, но была точка опрокидывания для относительно коротких строк, так как сортировка radix в решающей степени зависит от длины сортируемых строк.

Ответ 2

FYI, quicksort на самом деле O (n ^ 2), но со средним случаем O (nlogn)

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

Для графической демонстрации см.:

Ответ 3

Для еще большего удовольствия в подобном ключе попробуйте построить время, затраченное на n операций, на стандартную непересекающуюся структуру данных набора. Было показано, что асимптотически n & alpha; (n), где & alpha; (n) является инверсией функции log * n). Для любого номера, с которым вы, вероятно, столкнетесь как размер ввода, & alpha; (n) & le; 5 (и, действительно, log * n & le; 5), хотя он подходит к бесконечности асимптотически.

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

Ответ 4

Обычно алгоритмы O (n * log (n)) имеют 2-базисную логарифмическую реализацию.
Для n = 1024, log (1024) = 10, поэтому n * log (n) = 1024 * 10 = 10240 вычислений, увеличение на порядок.

Итак, O (n * log (n)) аналогична линейной только для небольшого количества данных.

Совет. Не забывайте, что quicksort очень хорошо работает на случайных данных и что он не является алгоритмом O (n * log (n)).

Ответ 5

Любые данные могут отображаться на линии, если оси выбраны правильно: -)

Википедия говорит, что Big-O - худший случай (т.е. f (x) есть O (N) означает, что f (x) "ограничено сверху" N) https://en.wikipedia.org/wiki/Big_O_notation

Вот хороший набор графиков, изображающих различия между различными общими функциями: http://science.slc.edu/~jmarshall/courses/2002/spring/cs50/BigO/

Производная от log (x) равна 1/x. Так быстро увеличивается log (x) по мере увеличения x. Он не линейный, хотя он может выглядеть как прямая линия, потому что он изгибается так медленно. Когда мы думаем о O (log (n)), я думаю об этом как O (N ^ 0 +), т.е. Наименьшая степень N, которая не является постоянной, так как любая положительная постоянная мощность N в конечном итоге настигнет ее. Это не на 100% точно, поэтому профессора будут злиться на вас, если вы это объясните.

Разница между журналами двух разных баз является постоянным множителем. Посмотрите формулу преобразования журналов между двумя базами: (под "изменением базы" здесь: https://en.wikipedia.org/wiki/Logarithm) Хитрость заключается в том, чтобы лечить k и b как константы.

На практике обычно есть некоторые икоты в любых данных, которые вы планируете. Там будут различия в вещах вне вашей программы (что-то подменяется в CPU впереди вашей программы, пропуски кэша и т.д.). Для получения надежных данных требуется много прогонов. Константы - самый большой враг, пытающийся применить нотацию Big O к фактическому времени выполнения. Алгоритм O (N) с высокой константой может быть медленнее алгоритма O (N ^ 2) при достаточно малых N.

Ответ 6

log (N) является (очень) примерно числом цифр в N. Таким образом, по большей части разница между log (n) и log (n + 1)

Ответ 7

Попробуйте построить фактическую линейную линию поверх нее, и вы увидите небольшое увеличение. Обратите внимание, что значение Y при 50,0000 меньше значения 1/2 Y при 100 000.

Он там, но он маленький. Вот почему O (nlog (n)) настолько хорош!