Как вы визуализируете разницу между O (log n) и O (n log n)?

Question

Бинарный поиск имеет среднюю производительность по случаю O(log n), а Быстрая сортировка с O(n log n) равна O(n log n) и O (n) + O (log n)

Answer 1

Представьте себе базу данных со всеми людьми в мире.Это 6,7 миллиардов записей.O (log n) - это поиск по индексированному столбцу (например, первичный ключ).O (n log n) возвращает всю совокупность в отсортированном порядке по неиндексированному столбцу.

• O (log n) было завершено до того, как вы прочитали первое слово этого предложения.1005 * O (n log n) все еще вычисляет ...

Другой способ представить это:

log n пропорционально количеству цифр в n.

n log n в n раз больше.

Попробуйте написать число 1000 один раз, а не тысячу раз.Первый занимает время O (log n), второй - время O (n log n).

Теперь попробуйте еще раз с 6700000000.Написание этого один раз все еще тривиально.Теперь попробуйте написать это 6,7 миллиардов раз.Даже если бы ты мог писать это раз в секунду, ты бы умер до того, как закончил.

Answer 2

Вы можете представить это на графике, см. здесь , например:

Answer 3

Нет, O(n log n) = O(n) * O(log n)

В математике, когда у вас есть выражение (например, e = mc ^ 2), если нет оператора, вы умножаете.

Обычно способ визуализации O (n log n) - это «сделать что-то, что займет log n вычислений n раз».

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

Answer 4

A (log n) участок увеличивается, но вогнутый вниз, что означает:

• Увеличивается при увеличении n
• Это скорость увеличения уменьшается когда n становится больше

A (n log n) участок увеличивается и (слегка) вогнут вверх, что означает:

• Увеличивается при увеличении n
• Это скорость увеличения (слегка) увеличивается, когда n становится больше

Answer 5

Зависит от того, хотите ли вы визуализировать n как имеющее конкретное значение.

Если вы склонны визуализировать n как имеющее конкретное значение, а единицами f(n) являются время или инструкции, тогда O(log n) в n раз быстрее O(n log n) для данной задачи размера n. Для единиц памяти или пространства, то O(log n) в n раз меньше для данной задачи размером n. В этом случае вы сосредотачиваетесь на кодомене f(n) для некоторых известных n. Вы визуализируете ответы на вопросы о том, сколько времени займет что-то или сколько памяти займет эта операция.

Если вы склонны визуализировать n как параметр, имеющий любое значение, то O(log n) в n раз масштабируется. O(log n) может выполнить n раз больше задач размером n. В этом случае вы сосредоточены на домене f(n). Вы визуализируете ответы на вопросы о том, какой большой n может получить или сколько экземпляров f(n) вы можете запустить параллельно.

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