Вопрос о большой O и большой омеге

Question

Я думаю, что это, вероятно, вопрос новичка о записи big-O. Скажем, например, у меня есть алгоритм, который рекурсивно разбивает весь список (O (n)), а затем собирает его обратно (O (n)). Я предполагаю, что это означает, что эффективность составляет O (n) + O (n). Упрощается ли это до 2O (n), O (2n) или O (n)? Из того, что я знаю об этой записи, это будет O (2n), и, используя правила асимптотической записи, вы можете отбросить 2, что дает эффективность O (n).

Если мы пытаемся найти нижнюю границу, может ли это правило все еще применяться? Если Ω (n) + Ω (n) = Ω (2n), можете ли вы отбросить 2? Я бы подумал, что нет, так как вы фактически снизили бы нижнюю границу (так как n <2n). </p>

Answer 1

Упрощается ли это до 2O (n), O (2n) или O (n)? "

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

2 * N пропорциональна N, поэтому, если максимальная стоимость не более чем пропорциональна 2 * N для достаточно большого N (O (2 * N)), максимальная стоимость такжене более чем пропорционально N для достаточно большого N (O (N)).

Если бы мы пытались найти нижнюю границу, может ли это правило по-прежнему применяться?

Наиболее определеннода.

2 * N пропорционально N, поэтому, если минимальная стоимость не менее чем пропорциональна 2 * N для достаточно большого N (Ω (2 * N)), минимальная стоимость также не будетменее чем пропорционально N для достаточно большого N (Ω (N)).

---

Например, допустим, у вас есть алгоритм, выполнение которого занимает 300 мс + 100 * N мс. Нижняя границаего скорость равна Θ (N) и, следовательно, Ω (N).

Что если выполнение алгоритма займет вдвое больше времени? Даже если это заняло 600 мс + 200 * Н мЧтобы выполнить, нижняя граница его скорости по-прежнему равна Θ (N) и, следовательно, Ω (N).

---

Самая важная вещь, которую нужно понять, чтобы понять Θ (N) и т.п., состоит в том, чтонотации используются для изучения того, насколько хорошо масштабируется .Этот один алгоритм занимает в два раза больше времени, чем другой ничего не говорит о том, насколько хорошо масштабируется любой из них, поэтому неудивительно, что они могут иметь одинаковое Ω () для нижней границы их скорости.

Answer 2

Это упростит - обычно до O (n), указывая, что количество времени, затрачиваемое на решение проблемы, пропорционально размеру проблемы. В этом случае может быть более целесообразно написать 2O (n), хотя это означает то же самое.

Answer 3

Я полагаю, согласно определению Big-O:

Если функция f (n) <= cg (n) для некоторой константы c и достаточно больших значений n, то это можно сказатьчто f (n) = O (g (n)).В вашем примере g (n) = n.</p>

Так, например, если можно выбрать какое-то значение для c, которое делает f (n) <= cn для достаточно большого n, то вы можете сказать, что f (n) = O (n).</p>

Большая Омега определяется аналогично.

Answer 4

Это было давно, но я думаю, что вы правы в обоих случаях.

UPDATE

На самом деле выглядит как Ω (n) + Ω (n) == Ω (n)