Big O сомнения в эффективности времени выполнения

Question

Считается ли O (n) более быстрым по сравнению с O (n log n)? Если у меня есть функция, которая делает цикл, то есть O (n), то сортировка слиянием вне цикла O (n log n) тогда время выполнения будет O (n log n), я полагаю?

Answer 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).

Answer 2

Когда 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 () состоит в том, чтобы упростить формулы времени выполнения, игнорируя все, кроме самого крупного компонента.

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

Answer 3

O (N) асимптотически «быстрее», когда N приближается к бесконечности, но для любого конечного значения N может быть медленнее, быстрее или равно.

Я не совсем уверен, что вы спрашиваетево втором предложении.Если вы имеете в виду, что часть алгоритма пропорциональна N log N, а другая - N, тогда да, big-O говорит, что вы игнорируете другие части, пока они добавляются к основной, а не умножаются на нее.

Answer 4

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), и это ваш случай.

Answer 5

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).