algorithm - 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 * 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) 基本上可以是任何东西。

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