大O符号时间问题

Question

我们有3个带有大符号的函数:

Func A: O(n)
Func B: O(n^2)
Func C: O(2^n)

如果这些函数在10秒内完成,那么需要为每个函数处理2*n个进程需要多长时间？如果你解释为什么我会快乐.

谢谢

Answer 1

实际上,你实际上只能用一个数据点来判断.举例来说,第一个的简单答案将是"两倍长",20秒,因为O(n)意味着时间复杂度与输入参数成正比地上升.

但是,这没有考虑到大O通常被简化为仅显示最高效果.所花费的实际时间可能与n加上常数5 成正比- 换句话说,有一个恒定的5秒设置时间,完全不依赖n,然后是每秒半秒n.

这意味着时间会是15几秒而不是20.并且,对于提到的其他情况,情况甚至更糟,因为O(n ²)实际上可能成比例,n^2 + 52n + 7这意味着您需要三个数据点,假设您甚至知道等式的所有分量.它甚至可能像以下一样可怕:

                  1      12
n^2 + 52*n + 7 + --- + ------
                  n    47*n^5

这在技术上仍然是O(n ²).

如果它们是简单的方程式(可能是作业),那么你只需要将方程组合在一起,然后在任何有n的地方插入2n,然后根据原始方法重新计算方程式:

Complexity  Equation     Double N     Time Multiplier
----------  --------   -------------  ---------------
O(n)        t = n      t = 2n               2
O(n^2)      t = n^2    t = (2n)^2
                         = 4 * n^2          4
O(2^n)      t = 2^n    t = 2^(2n)
                         = 2^n * 2^n        2^n
                                            (i.e., depends on
                                                  original n)

那么,我给出的答案就是:

• (A) 20秒;
• (B)40秒; 和
• (C)10 x 2 ⁿ秒.