algorithm - 大哦类之间的数学关系

我的教科书对这种关系的描述如下：
有一个很好的数学直觉也描述了这些类假设我们有一个算法，当输入大小为n时，运行时间为n0，当输入大小为2n时，运行时间为n1。我们可以根据n0和n1之间的关系来描述增长率：

Big-Oh      Relationship

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

这是为什么？

最佳答案

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