O (N log N) Сложность - похожа на линейную?

Question

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

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

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

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

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

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

Спасибо

Гав

Answer 1

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

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

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

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

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

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

Answer 2

К вашему сведению, быстрая сортировка на самом деле O (n ^ 2), но в среднем случае O (nlogn)

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

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

Answer 3

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

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

Answer 4

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

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

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

Answer 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)), я думаю о нем как о (N ^ 0 +), то есть о наименьшей степени N, которая не является константой, поскольку любая положительная постоянная степень N в конце концов обгонит ее. Это не на 100% точно, поэтому профессора будут злиться на вас, если вы объясните это так.

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

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

Answer 6

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

Answer 7

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

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