Big-Oh之间的数学关系类

Question

我的教科书是这样描述关系的：

There is a very nice mathematical intuition which describes these classes too. Suppose we have an algorithm which has running time N0 when given an input of size n, and a running time of N1 on an input of size 2n. We can characterize the rates of growth in terms of the relationship between N0 and N1:
Big-Oh      Relationship

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

这是为什么？

Answer 1

这是因为如果 f(n) 在 O(g(n)) 中，那么对于某些 k。

可以认为它的行为类似于 k * g(n)

例如，如果 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) 基本上可以是任何东西。

我个人认为这种粗略的直觉具有误导性，因此比无用更糟糕。其他人发现它非常有帮助。自己决定给它多少重量。

Answer 2

由于 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 3

基本上他们试图展示的只是在函数中用 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)²

Big-Oh之间的数学关系类

The Mathematical Relationship Between Big-Oh Classes

algorithm

complexity-theory

big-o