Умножение и добавление различных асимптотических обозначений - PullRequest
Новая
       13

Умножение и добавление различных асимптотических обозначений

4 голосов
/ 12 октября 2011

кто-нибудь знает, как выполнять такие вычисления Пример:

O(n^2) + THETA(n) + OMEGA(n^3) = ?

или

O(n^2) * THETA(n) * OMEGA(n^3) = ?

В общем, как складывать и умножать разные асимптотические обозначения?

Ответы [ 3 ]

5 голосов
/ 12 октября 2011

O дает верхняя граница ;

Ω дает нижнюю оценку ;

Θ дает асимптотическую оценку ;

В Википедии есть хорошая диаграмма, объясняющая это.

Следовательно, в общем они действительно несопоставимы.

Для вашего первого случая 

O(n^2) + Θ(n) + Ω(n^3)

Давайте сначала займемся O.Первый член говорит нам O(n^2), а второй член говорит нам O(n).Основываясь только на этих двух, мы знаем, что у нас есть O(n^2) для верхней границы.Тем не менее, третий термин ничего не говорит нам о верхней границе!Таким образом, мы действительно не можем сделать вывод о O.

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

Однако тривместе или даже просто O и Ω, оставляя вас в неведении, поскольку ни O, ни Ω не подразумевают ничего другого.

4 голосов
/ 12 октября 2011

Вы не можете.Предположим, вы знаете, что a > 0 и b < 10.Тогда у вас нет информации о a+b.Это может быть что угодно.

Big-O и Big-Omega действуют аналогично для функций.

1 голос
/ 12 октября 2011

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

O(n^2) + Theta(n) + Omega(n^3) = Omega(1)+Theta(n)+Omega(n^3) = Omega(n^3)

Это вытекает из предположения, что все функции положительные.То есть все функции Omega(1).

...