Математическая связь между классами Big-Oh

Question

Мой учебник описывает отношения следующим образом:

Существует очень хорошая математическая интуиция, которая также описывает эти классы.Предположим, у нас есть алгоритм, который имеет время выполнения N0 при заданном входе размера n и время выполнения N1 на входе размера 2n.Мы можем охарактеризовать темпы роста по соотношению между N0 и N1:

Big-Oh      Relationship

O(log n)    N1 ≈ N0 + c
O(n)        N1 ≈ 2N0
O(n²)       N1 ≈ 4N0
O(2ⁿ)       N1 ≈ (N0)²

Почему это так?

Answer 1

Поскольку O(f(n)) ~ k * f(n) (почти по определению), вы хотите посмотреть, что произойдет, если вы введете 2n для n.В каждом случае:

N1 ≈ k*log 2n = k*(log 2 + log n) = k*log n + k*log 2 ≈ N0 + c where c = k*log 2

N1 ≈ k*(2n) = 2*k*n ≈ 2N0

N1 ≈ k*(2n)^2 = 4*k*n^2 ≈ 4N0

N1 ≈ k*2^(2n) = k*(2^n)^2 ≈ N0*2^n ≈ N0^2/k

Итак, последнийвсе равно не совсем верно.Имейте в виду, что эти отношения истинны только асимптотически, поэтому аппроксимации будут более точными по мере увеличения n.Кроме того, f(n) = O(g(n)) означает только, что g(n) является верхней границей для f(n) для достаточно большого n.Так что f(n) = O(g(n)) не обязательно означает f(n) ~ k*g(n).В идеале, вы хотите, чтобы это было правдой, поскольку в этом случае ваша граница big-O будет жесткой.

Answer 2

По сути, они пытаются показать только простую алгебру после замены 2n на n в функциях.

O(log n)    
log(2n) = log(2) + log(n)
N1 ≈ c + N0

O(n)
2n = 2(n)        
N1 ≈ 2N0

O(n²)       
(2n)^2 = 4n^2 = 4(n^2)
N1 ≈ 4N0

O(2ⁿ)       
2^(2n) = 2^(n*2) = (2^n)^2
N1 ≈ (N0)²

Answer 3

Это потому, что если f(n) находится в O(g(n)), то его можно рассматривать как действующее как k * g(n) для некоторых k.

Так, например, если f(n) = O(log(n)), то оно действует какk log(n), а теперь f(2n) ≈ k log(2n) = k (log(2) + log(n)) = k log(2) + k log(n) ≈ k log(2) + f(n), и это ваше желаемое уравнение с c = k log(2).

Обратите внимание, что это грубая интуиция только .Пример того, где он ломается - это f(n) = (2 + sin(n)) log(n) = O(log(n)).Колеблющийся бит 2 + sin(n) означает, что f(2n)-f(n) может быть в принципе чем угодно.

Лично я считаю, что такая грубая интуиция вводит в заблуждение и поэтому хуже, чем бесполезна.Другие находят это очень полезным.Решите для себя, какой вес вы ему дадите.