给定一个真正的运行时,如何计算运行时复杂度("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)？

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的点数越多,就越能确定该函数.