Как Вы визуализируете различие между O (зарегистрируйте n), и O (n регистрируют n)?
Двоичный поиск имеет среднюю производительность случая как O(log n) и быстрая сортировка с O(n log n) O(n log n) то же как O (n) + O (зарегистрируйте n),
5 ответов
Представьте себе базу данных с каждым человеком в мире. Это 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).
Теперь попробуйте повторить это с 67000000. Записать его один раз все еще тривиально. Теперь попробуйте записать его 6,7 миллиарда раз. Даже если бы вы могли написать его один раз в секунду, вы бы умерли, не закончив.
Вы можете визуализировать это в виде графика, см. здесь , например:
Зависит от того, склонны ли вы визуализировать 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) вы можете запустить параллельно.
Ни одна из точек зрения не лучше другой. Первый можно использовать для сравнения подходов к решению конкретной проблемы. Последнее можно использовать для сравнения практических ограничений данных подходов.
График A (log n) увеличивается, но имеет вогнутый вниз, что означает:
- Он увеличивается, когда n становится больше
- Это скорость увеличивается уменьшается когда n становится больше
A (n log n) график увеличивается и (слегка) вогнут вверх, что означает:
- Он увеличивается, когда n становится больше
- Это скорость увеличения (незначительно) увеличивается при увеличении n
Нет, 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