#algorithm #big-o
#алгоритм #big-o
Вопрос:
Считается ли O (n) быстрее по сравнению с O (n log n)? Если у меня есть функция, которая выполняет цикл, который равен O (n), то сортировка слиянием вне цикла O (n log n), тогда время выполнения будет O (n log n) Я полагаю?
Комментарии:
1. Есть ли опечатка в вашем вопросе? Неясно, что такое бит O (n log n).
2. извините, я немного прояснил вопрос
Ответ №1:
Считается ли O (n) быстрее по сравнению с O (n log n)?
Нет, не напрямую. Нотация Big-O — это ограничивающий фактор в алгоритме, который больше связан с масштабируемостью алгоритмов, чем со скоростью. У вас может быть процедура O (1), которая занимает больше времени, чем процедура O (n ^ 2) для определенного набора данных, но первая будет масштабироваться намного лучше.
При этом, как правило, O (n), конечно, будет масштабироваться лучше, чем O (n log n), и, вероятно, будет считаться «быстрее» или «лучше».
Если у меня есть функция, которая выполняет цикл, который равен O (n) a O (n log n), тогда время выполнения будет O (n log n) Я полагаю?
Неясно, что именно вы здесь говорите —
Если вы имеете в виду, что у вас есть цикл с 2 функциями, т.Е.:
Loop over N elements
- Call O(n) function
- Call O(n log n) function
Тогда общий ограничивающий фактор будет равен O (n ^ 2 log n).
(Из комментария)
Я имею в виду, что сортировка слиянием (n log n) находится вне цикла, так что все равно это будет O (n log n)
Если вместо этого вы говорите, что собираетесь сделать что-то вроде:
- Call O(n log n) function
- Loop over N elements
- Process each element using O(1) algorithm
Тогда общая сложность по-прежнему равна O (n log n), поскольку это является ограничивающим фактором. Это потому, что «O (n n)» по-прежнему равно O (n).
Ответ №2:
O (n) асимптотически «лучше» или «быстрее», чем O (n log n), да. Если у вас есть функция, которая выполняет цикл, и тело цикла вызывает функцию O (n log n) n раз, общая сложность составляет O (n ^ 2 log n)… если я не неправильно истолкую ваш вопрос. Другими словами, выполнение O (n log n) n раз приводит к O (n * n log n) = O (n ^ 2 log n) сложности.
Комментарии:
1. Я имею в виду, что сортировка слиянием (n log n) находится вне цикла, так что все равно это будет O (n log n)
2. @xonegirlz: Не могли бы вы опубликовать какой-нибудь код, чтобы я понял, что вы говорите? Извините за плотность.
Ответ №3:
O (n * log n), конечно, больше, чем O (n).
O (n * n * log n)> O (n * n)> O (n * log n) > O (n)> O (1)
И так далее.
O (n 1) = O (n)
O (2 * n) = O (n)
O (n log n) = O (n)
O (n n * log n) = O (n * log n) и это ваш случай.
Ответ №4:
O (N) асимптотически «быстрее», поскольку N приближается к бесконечности, но для любого конечного значения N может быть медленнее, быстрее или равно.
Я не совсем уверен, о чем вы спрашиваете во втором предложении. Если вы имеете в виду, что часть алгоритма пропорциональна N log N, а другая — N, тогда да, big-O говорит, что вы игнорируете другие части, пока они добавляются к основной, а не умножаются на нее.
Ответ №5:
По мере того, как n становится больше, log n увеличивается без ограничений. Это означает:
- O (log n)> O (1), поэтому O (log n 1) = O (log n)
- O (n log n n) = O (n (log n 1)) = O (n log n)
Вся идея нотации O () состоит в том, чтобы упростить ваши формулы во время выполнения, игнорируя все, кроме самого большого компонента.
С другой стороны, это также позволяет вам игнорировать постоянные факторы в вашем более крупном компоненте. Итак, только потому, что алгоритм асимптотически быстрее для больших задач, не означает, что он на самом деле быстрее для какой-либо конкретной задачи…