算法

算法五个重要特性

有穷性 一个算法必须总是在有穷步之后结束，且每一步都可以在有穷时间内（合理时间内）完成。
确定性 算法中每一条指令必须有确切的含义。并且在任何条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的结果。
可行性
输入
输出

算法设计的要求

正确性 算法应当满足具体问题的需求。
可读性 算法主要是为了人的阅读与交流，其次才是机器执行。
健壮性 当输入数据非法时，算法也能适当地做出反应或进行处理。
效率与地存储需求量 高效率，低存储。

要求制作一个程序。一个人做的程序运行时间为500ms，所占内存为5M；另一个人做的程序的运行时间为5s，所占内存为500M。很明显，第一个人做的程序更好。
衡量算法的好坏包括两个重要指标：运行时间和占用内存。

时间复杂度

算法的时间复杂度是指执行算法所需要的计算工作量。

代码的绝对执行时间是无法估计的。但我们可以通过预估出代码的基本操作执行次数
一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数f(n)，算法的时间量度记作T(n)=O(f(n))。它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐进时间复杂度，简称时间复杂度。
也会被称为大O表示法。O表示"on the order of（在……阶）"。

定义

若存在函数f(n),是的当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n))，称O(f(n))为算法的渐进时间，建成时间复杂度。

简单来说

时间复杂度就是把时间规模T(n)简化为一个数量级，这个数量级可以是n，n^2，n3等等（假设n无限大）。

原则

如果运行时间是常数数量级，用常数1表示；
只保留时间函数中的最高阶项；
省去最高阶项系数。

案例分析

计算两个N*N矩阵相乘的算法

for( i = 0; i <= n; i++ ) {
    for( j = 0; j <= n; j++ ) {
        c[i][j] = 0;    //执行次数：n^2
        for( k = 0; k <= n; k++ ) {
            c[i][j] += a[i][k] * b[k][j]    //执行次数：n^3
        }
    }
}

算法中重复执行的次数，可以计算出T(n)=n³⁺ⁿ2(n的三次方为T(n)的同数量级)。
根据上面的原则推导时间复杂度为T(n)=n^3

分析策略

根据案例分析，我们可以大概总结：从内向外分析，从最深层次开始分析。

常见的时间复杂度

常见函数增长率

空间复杂度

定义

空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的度量，记作S(n)=O(f(n))。其中n为问题的规模（或大小）。

计算原则

一个执行的程序除了需要存储空间来寄存本身所用指令、常数、变量和输入数据外，也需要一些对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间。
若输入数据所占空间只取决于问题本身，和算法无关，则只需要分析出输入和程序之外的额外空间，否则应同时考虑输入本身所需空间（和输入数据的表示形式有关）。若额外空间相对于输入数据量来说是常数，则称此算法为原地工作。
因为现在硬盘的存储空间都比较大，一般不会因为一点空间的大小对算法大动干戈，更多的是想怎么实现优化算法的时间复杂度。但对于数据量较大的，空间复杂度也显得尤为重要。

案例

计算1!
```
{
    x = 1;  //只运行一次
}
```
时间复杂度 O(1)
空间复杂度 O(1)

计算10!

{
    int n = 11, num =  1;
    for( int i = 1; i < n; i++ ){
        num *= i;   //运行n次
    }
}

时间复杂度 O(n)
空间复杂度 O(1)

计算10!*9!...2!*1!

{
    int n = 11; sum = 0;
    for( int i = 1; i < n; i++ ){
        int num = 1;
        for( int j = 1; j <= i; j++ ) {
            num *= i;   //运行n^2次
        }
        sum += num;     //运行n次
    }
}