一、什么是算法

1.1 算法和程序的区别

算法的定义：

计算或解决问题的步骤和思想。可以将算法比喻做食谱，想要做出特定的料理就要遵循食谱上的步骤。同理，要解决特定的问题就要遵循特定的方法；也即算法。
- 例如：
  - 将随意排列的数字按从小到大的顺序排列。
  - 寻找出发点到终点的最短距离。
- 算法和食谱的区别
  - 算法是严密的，严谨的。
  - 算法的步骤都是用数学的方式来描述，十分明确。
程序的定义：

计算机能够理解的编程语言编写而成，可以在计算机上运行的代码。
二者的区别与联系：
- 算法是以人类可以理解的方式描述
- 程序=算法+数据结构

1.2 算法设计

计算机擅长高速执行的一些基本命令，但是无法执行复杂命令。

基本命令指：

做加法
在指定的内存地址保存数据
……

计算机是以这些基本命令组合为基础进行运算，面对复杂的操作，也要通过这些命令的搭配来应对。

设计算法就是搭配计算机可以执行的基本命令来实现某个算法。

1.3 算法的选择

解决一个问题的方法有很多，那么就会有很多的算法可以解决同一个问题。如何选择？

易于理解
容易被编写成程序
运行时不需要太大的空间资源
算法执行时间(算法考量最为重要的指标)

1.4 算法的特性

有穷性

一个算法必须在执行有穷步骤之后结束，且每一步都在有穷时间完成。
确定性

算法每一条指令必须有确切的含义，不产生二义性。即对于相同的输入只能得到相同的结果
可行性

算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。
输入

一个算法至少有零个输入
输出

一个算法至少有一个输出

二、算法的执行效率

2.1 时间复杂度

算法需要执行的运算次数用输入大小n 的函数表示，即 T(n) 。
用来度量算法的运行时间，记作: O(T(n))。它表示随着输入大小n的增大。称作算法的时间复杂度

算法时间复杂度的计算：

我们知道常数项对函数的增长速度影响并不大，所以当 T(n) = c，c 为一个常数的时候，我们说这个算法的时间复杂度为 O(1)
我们知道高次项对于函数的增长速度的影响是最大的。当T(n)=n^a+n(a-1)+……+n+c ,（a,c为常数)时，算法时间复杂度为O(n^a)
为函数的阶数对函数的增长速度的影响是最显著。当T(n)=n!+n^a+n(a-1)+……+n+c，(a,c为常数)时，算法时间复杂度为O(n!)

算法时间复杂度计算规则：

对于一个循环，假设循环体的时间复杂度为 O(n)，循环次数为 m，则这个循环的时间复杂度为 O(n×m)。

void aFunc(int n) {
    for(int i = 0; i < n; i++) {         // 循环次数为 n
        printf("Hello, World!\n");      // 循环体时间复杂度为 O(1)
    }
}

此时时间复杂度为 O(n × 1)，即 O(n)。c

对于多个循环，假设循环体的时间复杂度为 O(n)，各个循环的循环次数分别是a, b, c...，则这个循环的时间复杂度为 O(n×a×b×c...)。分析的时候应该由里向外分析这些循环。

void aFunc(int n) {
    for(int i = 0; i < n; i++) {         // 循环次数为 n
        for(int j = 0; j < n; j++) {       // 循环次数为 n
            printf("Hello, World!\n");      // 循环体时间复杂度为 O(1)
        }
    }
}

此时时间复杂度为 O(n × n × 1)，即 O(n^2)。

对于顺序执行的语句或者算法，总的时间复杂度等于其中最大的时间复杂度。

void aFunc(int n) {
    // 第一部分时间复杂度为 O(n^2)
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            printf("Hello, World!\n");
        }
    }
    // 第二部分时间复杂度为 O(n)
    for(int j = 0; j < n; j++) {
        printf("Hello, World!\n");
    }c
}

此时时间复杂度为 max(O(n^2), O(n))，即 O(n^2)。

对于条件判断语句，总的时间复杂度等于其中时间复杂度最大的路径的时间复杂度。

void aFunc(int n) {
    if (n >= 0) {
        // 第一条路径时间复杂度为 O(n^2)
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                printf("输入数据大于等于零\n");
            }
        }
    } else {
        // 第二条路径时间复杂度为 O(n)
        for(int j = 0; j < n; j++) {
            printf("输入数据小于零\n");
        }
    }
}

2.2 示例

求该方法的时间复杂度

void aFunc(int n) {
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            printf("Hello World\n");
        }
    }
}

参考答案：当 i = 0 时，内循环执行 n 次运算，当 i = 1 时，内循环执行 n - 1 次运算……当 i = n - 1 时，内循环执行 1 次运算。所以，执行次数 T(n) = n + (n - 1) + (n - 2)……+ 1 = n(n + 1) / 2 = n^2 / 2 + n / 2。根据上文说的大O推导法可以知道，此时时间复杂度为 O(n^2)。

求该方法的时间复杂度
```
void aFunc(int n) {
    for (int i = 2; i < n; i++) {
        i *= 2;
        printf("%i\n", i);
    }
}
```
参考答案：假设循环次数为 t，则循环条件满足 2^t < n。可以得出，执行次数t = log(2)(n)，即 T(n) = log(2)(n)，可见时间复杂度为 O(log(2)(n))，即 O(log n)。
求该方法的时间复杂度
```
long aFunc(int n) {
    if (n <= 1) {
        return 1;
    } else {
        return aFunc(n - 1) + aFunc(n - 2);
    }
}
```
参考答案：显然运行次数，T(0) = T(1) = 1，同时 T(n) = T(n - 1) + T(n - 2) + 1，这里的 1 是其中的加法算一次执行。显然 T(n) = T(n - 1) + T(n - 2) 是一个斐波那契数列,通过归纳证明法可以证明，当 n >= 1 时 T(n) < (5/3)^n，同时当 n > 4 时 T(n) >= (3/2)^n。所以该方法的时间复杂度可以表示为 O((5/3)^n)，简化后为 O(2^n)。

01-算法的基本概念