复杂度 0 符号

Question

我对这个问题有点困惑，希望得到一些指导：

An O(n2) function takes approx 1 second to run when N is 10000.

How long will it take when N is 30000?

我在想要么也是 1 秒，要么是 3 秒，因为它是三倍大，但我不确定我的逻辑是否正确。

谢谢。

Answer 1

In computer science, the time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the length of the string representing the input.

这样，如果复杂度为 O(n^2) 且输入为 3 倍，则工作时间为 3^2 = 9 倍。工作时间为 9 秒。

Answer 2

题目问题较多

第一个问题：时间复杂度一般不以秒为单位衡量时间。例如，排序算法的时间复杂度可能指比较（或交换）的次数，散列 table 查找的时间复杂度也可能指执行的比较次数。实际运行时间是否与这些测量值成正比尚不确定table。

第二个问题：big-O的定义是这样的：

f(n) = O(g(n)) if there's N and k such that n > N implies f(n) < k*g(n).

这是个问题，因为即使这种情况下的运行时间以秒为单位，将定义应用于 O(n^2) 也只是说对于足够大的 n，该函数的边界是 n^ 的某个倍数2.

因此不能保证 10000 和 30000 足够大以符合 "big enough" 的要求，即使是，您也无法从单个数据点开始估计 k。即使有了这个估计，你也只能得到一个上限。

这个问题大概想问的是这个：

Suppose that a function runs in time approximately proportional to n^2. It takes 1 second when n=10000. Approximately long does it take when n=30000?

然后，可以求解方程组：

1 sec ~= k * 10000^2
answer ~= k * 30000^2
        = 3^2 * k * 10000^2
        ~= 3^2 * 1 sec
        = 9 sec

复杂度 0 符号

Complexity 0 Notation

python

big-o

time-complexity