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

Ответ 1

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

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

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

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

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

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

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

Ответ 2

Вы можете визуализировать его в сюжете, см. здесь, например:

Ответ 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

Ответ 4

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

• Он увеличивается, когда n становится больше
• Скорость увеличения когда n становится больше

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

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

Ответ 5

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

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

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

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