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

Question

我试着尽快问一下:

我有一个算法，作为一个函数，我们称它为f:

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

现在，我有一个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)？

Answer 1

对于不同的 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，您拥有的点数越多，您就越能确定该函数。