02 时间复杂度如何计算?
待兔 437 4

我们想要知道一个算法的时间复杂度,很多人首先想到的的方法就是把这个算法程序运行一遍,那么它所消耗的时间就自然而然知道了。

这种方式可以吗?当然可以,不过它也有很多弊端。 这种方式非常容易受运行环境的影响,在性能高的机器上跑出来的结果与在性能低的机器上跑的结果相差会很大。而且对测试时使用的数据规模也有很大关系。再者,并我们在写算法的时候,还没有办法完整的去运行呢。

因此,另一种更为通用的方法就出来了:大O符号表示法 ,即 T(n) = O(f(n))

我们先来看个例子:

for(i=1; i<=n; ++i)
{
   j = i;
   j++;
}

通过「 大O符号表示法」,这段代码的时间复杂度为:O(n) ,为什么呢?

从上面代码可以看到,在while循环里面,每次都将 i 乘以 2,乘完之后,i 距离 n 就越来越近了。我们试着求解一下,假设循环x次之后,i 就大于 2 了,此时这个循环就退出了,也就是说 2 的 x 次方等于 n,那么 x = log2^n 也就是说当循环 log2^n 次以后,这个代码就结束了。因此这个代码的时间复杂度为:O(logn)

线性对数阶O(nlogN)

线性对数阶O(nlogN) 其实非常容易理解,将时间复杂度为O(logn)的代码循环N遍的话,那么它的时间复杂度就是 n * O(logN),也就是了O(nlogN)。

就拿上面的代码加一点修改来举例:

for(i=1; i<n; i++)
{
    i = 1;
    while(i<n)
    {
        i = i * 2;
    }
}

平方阶O(n²)

平方阶O(n²) 就更容易理解了,如果把 O(n) 的代码再嵌套循环一遍,它的时间复杂度就是 O(n²) 了。 举例:

for(x=1; i<=n; x++)
{
   for(i=1; i<=n; i++)
    {
       j = i;
       j++;
    }
}

这段代码其实就是嵌套了2层n循环,它的时间复杂度就是 O(n*n),即 O(n²) 如果将其中一层循环的n改成m,即:

for(x=1; i<=m; x++)
{
   for(i=1; i<=n; i++)
    {
       j = i;
       j++;
    }
}

那它的时间复杂度就变成了 O(m*n)

立方阶O(n³)、K次方阶O(n^k)

参考上面的O(n²) 去理解就好了,O(n³)相当于三层n循环,其它的类似。

除此之外,其实还有 平均时间复杂度、均摊时间复杂度、最坏时间复杂度、最好时间复杂度 的分析方法,有点复杂,这里就不展开了。

评论区

索引目录