Как рассчитать обозначение Big Oh

Question

Пожалуйста, кто-нибудь может подсказать, как рассчитывается 2n = O(3n)?

Вот еще несколько примеров:

2^4 = O(1)
10n = O(n)
n log2(n) = O(n log n)

Answer 1

Существует строгое математическое определение big-O:

f ( x ) - O (г ( x )), если существуют значения x0 > = 0 и k > 0 такое, что для всех x > x0 , f ( x ) <= k * g (<em> x ).

Чтобы доказать утверждения о классификации функций big-O, вы должны показать, как найти значения x0 и k .

Answer 2

2^4 = 2^4 * 1 <= 2^4 * 1

так 2^4 равно O(1) с постоянной 2^4.

10 * n = 10 * n <= 10 * n

так 10 * n равно O(n) с постоянной 10.

n log2 n = n log n / log 2 <= (1 / log 2) * n log n

так n log2 n равно O(n log n) с постоянной 1 / log 2.

Answer 3

Вообще говоря, используйте определение асимптотической записи, затем предоставьте доказательство того, что f (n) = O (g (n)), где f (n) - ваша функция, а g (n) - граница, которой вы являетесьпытаясь доказать.

Для вашего первого примера:

2n =? O(3n)
f(n) = 2n, g(n) = 3n
need c such that for n > n0, f(n) <= c*g(n); guess c = 1
We have f(n) = 2n <= 3n = c*g(n) for n >= 0, so
2n = f(n) = O(g(n)) = O(3n)

Для вашего второго примера:

2^4 =? O(1)?
f(n) = 2^4, g(n) = 1
need c such that for n > n0, f(n) <= c*g(n); guess c = 2^4 + 1
We have f(n) = 2^4 <= 2^4 + 1 = c*g(n), so
2^4 = f(n) = O(g(n)) = O(1)

Ваш третий пример практически эквивалентен первому.

Ваш четвертый пример неверен;неверно, что

n log^2(n) = O(n log n)

Это правда, что

n log(n^2) = O(n log n)

Но это другое выражение.Чтобы увидеть, что n log ^ 2 (n) не является O (n log n), мы можем поспорить так: пусть c - произвольная фиксированная постоянная.Мы можем найти такое n, что c * n * log (n)

c*n*log(n) < n*log^2(n)
c < log(n)

Так что выберите n = 2 ^ (c + 1).Следовательно, не существует такого n0, чтобы при n> n0 f (n) <= c * g (n). </p>

РЕДАКТИРОВАТЬ: в четвертом примере, если вы имеете в виду «log2 (n)»log-base-two из n, тогда да, nlog2 (n) = O (nlogn).Обычно при выполнении алгоритмических сложностей логарифм понимается как основание два, если не указано иное.Извините за путаницу.

Answer 4

Есть несколько способов доказать это:

Можно использовать ограничение:

f (n) = O (g (n)), если выполняется следующее:

                f(n)
   limsup    ----------  < infinity
x->infinity     g(n)

Итак, если вы берете 2n/(3n) в пределе, это 1.5.