• 算法概述
• 算法复杂度分析
  • 时间复杂度
    • 1. 问题规模与语句频度
    • 2. 时间复杂度
    • 3. 算法复杂度的分析与计算
    • 4. 最好最坏和平均时间复杂度
  • 空间复杂度

算法概述

• 算法：是为了解决某类问题而规定的一个有限长的操作序列。
• 算法五大特性：
  1. 有穷性：算法必须能在执行有限个步骤之后终止；
  2. 确切性：算法的每一步骤必须有确切的定义；
  3. 可行性：计算都可以在有限时间内完成（也称之为有效性）。
  4. 输入：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件；
  5. 输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；
• 算法设计要求
  1. 正确性：对合法的输入得到正确的结果
  2. 可读性：算法便于理解交流
  3. 收敛性：目标量收敛，即趋于平稳
  4. 健壮性：输入数据非法时，能做出正确的反应或进行处理。
  5. 效率与低储存要求：（时\空效率）

算法复杂度分析

时间复杂度

算法时间的度量

一个用高级语言编写的程序所耗费的时间一般取决于：

1. 算法设计
2. 问题规模
3. 所使用高级语言
4. 编译程序（解释程序）
5. 硬件速度

1. 问题规模与语句频度

不考虑计算机软硬件等环境因素，影响算法时间代价最主要的因素是问题规模，或者说它是问题规模的函数f(n)。

• 问题规模是算法求解问题输入量的多少，一般用整数n表示，而问题规模n对不同的问题含义不同。 算法执行时间 = 语句执行时间的总和，语句执行时间 = 语句的执行次数(频度)*执行一次时间。
• 一条语句重复执行的次数称作语句频度。

例：

for (i=1;i<=n;i++)       // 频度 n+1
    for (j=1;j<=n;j++)   // 频度 n*(n+1)
    {                    
        c[i][j]=0;                           // 频度n^2
        for(k=1;k<=n;k++)                    // 频度n^2*(n+1)
        c[i][j]=c[i][j]+a[i][k]*b[k][j];     // 频度n^3
    }

该算法语句频度之和

2. 时间复杂度

对于比较简单的算法可以直接计算出所有语句的频度，但对于稍微复杂算法，的可以选择一个基本语句，以此语句的频度，作为算法运行时间的衡量准则。

• 基本语句： 指算法中重复执行的次数与算法执行时间成正比的语句，他对算法运行时间影响最大。
• 通常，算法的执行时间随着问题规模的增长而增长，这样我们只需考虑问题规模增长的趋势，即当问题规模足够大的时候，算法基本语句的执行次数在渐进意义下的阶，所以我们给出大O记号的定义。
• 大O符号：一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),如果存在正常数c和n0使得当N≤n0时T(N)≥cf(N),则记为T(N)=O(f(N))。 即

大O符号是一种算法复杂度的相对表示方式(“O”是Oder的首字母，表示“阶”或者“数量级”)。大O记号的思想在于简化分析过程，比如二次多项式我们都可以看作是O(n^2)，因为低次项和二次项系数随着n的增长会变得无足轻重。

3. 算法复杂度的分析与计算

1. 找出所有语句中语句频度最大的那条语句作为基本语句
2. 计算基本语句的频度得到问题规模的某个函数f(n)
3. 取其数量级用符号“O”表示即可

• 一些规则

常见非递归算法的时间复杂度举例

• 常量阶T(n)=O(1)

for( i=0; i<10000; i++){
    x++;
    s=0;   // 算法的执行时间不随问题规模n增长而增长
    }

• 对数阶T(n)=O(logn)

for( i=1; i<=n; i=i*2){
    x++；
    s=0
}

• 线性阶T(n)=O(n)

for( i=0; i<0; i++){
    x++；
    s=0
}

• 立方阶T(n)=O(n^3)

for( i=1; i<=n; i++ )
    for( j=1; j<=n; j++)
        for( k=1; k<=j; k++)
            x=x+1;
    /* 多数情况下，当若干个循环语句时，算法的时间复杂度是由最深层循环
    内的基本语句的频率f(n)决定的 */

计算

其他常用函数阶：

一般来说，指数阶与组合阶的复杂度效率是无法忍受的，复杂度为c 、 log2n 、n 、 n*log2n,那么这个算法时间效率比较高，出现更多的是多项式时间的复杂度。

4. 最好最坏和平均时间复杂度

通常只讨论算法在最坏的时候的时间复杂度，及分析算法执行时间的上界。

空间复杂度

定义：S(n) = O(f(n))

表示表示随着问题规模n的增大，算法运行所需的增长率与g(n)的增长时间相同。 算法要占据的空间包括

1. 算法本身要占有的空间，指令，常数，变量以及输入要处理的数据等
2. 算法要使用的辅助空间

例：逆序数组中的元素

for( i=0; i<n/2; i++)
{
    t=a[i];
    a[i]=a[n-i-1];
    a[n-i-1]
}  // t占有的为的辅助空间

S(n)=O(1)

for(i=0, j=n-1; i<n; i++, j++)
    b[j]=a[i];
for(i=0; i<n; i++)
    a[i]=b[i];  //b[]占有的为辅助空间

S(n)=O(n)b

• Ω()是复杂度的下界，O()是复杂度的上界，θ()既是上界又是下界