算法复杂度

概述

计算机算法里面，最最基础的就是算法复杂度概念的建立。这个是算法书第一章节要讲清楚的。本章就是介绍这块相关的知识。

衡量的维度

性能测量 performance measurement，分为空间复杂度 space complexity，时间复杂度 time complexity。

最坏情况、平均情况分析和增长的量级。

空间复杂度

指令空间 instruction space，数据空间 data space，环境栈空间 environment stack space。

时间复杂度

大O符号表示法：即 T(n) = O(f(n))。

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

实际上执行的次数应该是T(n)=times(1+2n)，当n取向无穷大的时候，+1和2的效用将会减弱，我们就可以忽略成O(n)复杂度。

常见的时间复杂度有这几种：

常数阶O(1)

int i = 1;
int j = 2;
++i;
j++;
int m = i + j;

可能有多行代码，但是复杂度和无穷大的n比起来还是小。

对数阶O(logN)

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

线性阶O(n)

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

线性对数阶O(nlogN)

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

平方阶O(n²)

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

立方阶O(n³)
K次方阶O(n^k)
指数阶(2^n)

引用

• [1] 算法复杂度-百度百科
• [2] 时间复杂度-百度百科