Вопрос про большой O и большой Omega

Я думаю, что это, вероятно, вопрос новичка о нотации большого 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).


analysis big-o asymptotic-complexity
person A D    schedule 14.07.2011    source источник

Ответы (4)


arrow_upward
2
arrow_downward

Does this simplify to 2O(n), O(2n), or O(n)?"

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

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

If we were trying to find a lower bound, though, can this rule still apply?

Определенно да.

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

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

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

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

person ikegami    schedule 14.07.2011

arrow_upward
1
arrow_downward

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

person Community    schedule 14.07.2011

arrow_upward
0
arrow_downward

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

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

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

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

person Kevin D.    schedule 14.07.2011

arrow_upward
0
arrow_downward

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

ОБНОВЛЕНИЕ

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

person Abdullah Jibaly    schedule 14.07.2011
comment
Вы имеете в виду, что в последнем случае нижняя граница равна Ω(2n)? - person A D; 14.07.2011
comment
Нет, похоже, что вы можете отказаться от констант с большой омегой. См.: cs.odu.edu/~toida/nerzic/ контент/функция/growth.html - person Abdullah Jibaly; 14.07.2011