performance - 给定实际运行时如何计算运行时间复杂度（`"O(m)"`）？

Question

我试着很快问它：

我有一个算法，作为一个函数，我们称之为f：

void f(int[1..N]) {
   // algorithm goes here
}

现在，我有real runtime一个N输入。

请假设该函数time()以毫秒为单位返回当前系统的时间。

int[1...N] n;
unsigned long start = time(), end; 
f(N); 
end = time();
printf("Real runtime: %ul", end - start);

所以换句话说，我知道f参数会运行多少毫秒N。

通过这些信息，我如何计算f(N)运行时间复杂度，即f = O(N)？

score 5 · Accepted Answer

对于不同的 N，您将需要多个数据点。

假设你得到这些统计数据：

N     time(ms)
4       12
8       24
16      48

在这种情况下，将 N 加倍会使时间加倍，因此您的复杂度必须为 O(N)。

但如果你得到这些统计数据

N     time(ms)
4       16
8       64
16      256

在这种情况下，将 n 加倍会使运行时间增加四倍，因此您的复杂度必须为 O(n2)。

如果时间根本没有改变，你的复杂度是 O(1)

同样，不同的数据点会让您确定满足 big(O) 的函数。对于不同的 N，您获得的点数越多，您就可以更好地确定该函数。

1 回答 1