算法

算法的基本概念

程序 = 数据结构 + 算法

数据结构解决如何正确地描述现实世界的问题，并存入计算机

算法则关注如何高效的处理这些数据以解决实际问题（求解问题的步骤）

算法的定义

算法是对特定问题求解步骤的一种描述，他是指令的有限序列，其中的每条指令表示一个或多个操作

算法的特性

有穷性

一个算法必须总在执行有穷步之后结束，且每一步都可在有穷时间内完成

算法必须有穷，程序可以是无穷的

确定性

算法中的每条指令必须具有明确的含意，对于相同的输入只能得出相同的输出

可行性

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

输入

一个算法有零个或多个输入，这些输入取自于某个特定的数据对象的集合

输出

一个算法有一个或多个输出，这些输出是与输入有着某种特定关系的量

“好”的算法需要具备的特质

正确性

能够正确地解决问题

可读性

能够有良好的可读性，以便帮助人们理解（写代码有注释）

健壮性

输入非法输入时，算法能适当地做出反应或进行处理，而不会产生莫名其妙的输出结果

高效率和低存储量需求

花的时间少，不费内存，空间复杂度低

算法的时间复杂度

事前预估算法的时间开销 $T(n)$ 与问题规模 $n$ 的关系 ( $T$ 表示 $time$ )

比如下面这一段示例代码

void LoveYou(int n) { // n 为问题规模
    int i; // 起始数
    while (i <= n) { // 执行 3001 次
        i++; // 执行 3000 次
        printf("I Love You %d\n", i); // 执行 3000 次
    }
    printf("I Love More Then %d\n", n); // 执行一次
}

int main () {
    LoveYou(3000);
}

由此可得该程序的时间复杂度 $T(3000) = 1 + 3001 + 2 * 3000 + 1$

使用时间开销与问题规模 $n$ 之间的关系则可以表达为 $T(n) = 3n + 3$

简化时间开销与问题规模间的关系

由于在代码过于复杂的情况下，清楚的写出如上面表达式的时间复杂度表达式过于困难，因此需要某些手段简化这一表达

我们可以使用时间复杂度的数量级 $ O(n) $ 来表示时间复杂度，即当 $ n $ 趋近于无限时，表达式中数量级较大的那一项可以约等于总数，而小的那几项可以直接抛弃掉，只留下最大数量级的项 ，严谨数学表达为：

$$T(n) = O\big(f(n)\big) \Leftrightarrow \lim\limits_{n\to\infty} \frac{T(n)}{f(n)} = k$$

即当 $n$ 趋近于无限时，时间开销与 $f(n)$ 的表达式之比应该是某个常数（对于时间复杂度只需要关注阶数高的那一项，并且去掉其系数即可）

基于这一原理可以推出以下两种计算准则

加法准则

多项相加，只保留最高阶项，且系数变为1，其余项去除

表达式为：

$$T(n) = T_1(n) + T_2(n) = O\big(f(n)\big) + O\big(g(n)\big) = O\Big(\max\big(f(n), g(n)\big)\Big)$$

具体例子如：

$$T(n) = n^3 + n^2 + 99999 = O(n^3) + O(n^2) + O(1) = O(n^3)$$

乘法准则

对于两个含有 $n$ 的项相乘，对应的时间复杂度也需要进行相册

表达式为：

$$T(n) = T_1(n) \times T_2(n) = O\big(f(n)\big) \times O\big(g(n)\big) = O\big(f(n) \times g(n)\big)$$

具体例子为：

$$T_3(n) = n^3 + n^2\log_2n = O(n^3) + O(n^2) \times O(\log_2n) = O(n^3) + O(n^2\log_2n)$$

算法复杂度数量级大小排序

$$O(1) < O(\log_2n) < O(n) < O(n\log_2n) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)$$

对于上面那个例子，最后运用加法规则保留最高阶时间复杂度时，判断 $O(n^3)$ 和 $O(n^2\log_2n)$ 哪一个大时，就需要使用上面的大小排序

$n^3$ 可以分解成 $n \times n^2$ ，同样的 $n^2\log_2n$ 也可以分解为 $n^2 \times \log_2n$ ，这时只需要比较 $n$ 和 $\log_2n$ 的大小就行了，显而易见的应该保 $n$，所以最终的时间复杂度为 $O(n)$

对于下面这个例子：

void LoveYou(int n) { // n 为问题规模
    int i; 
    while (i <= n) { 
        i++; 
        printf("I Love You %d\n", i); 
        for (int j = 1; j <= n; j++) {
            printf("I love Iron Man"); // 内层循环 $ n^2 $ 次
        }
    }
    printf("I Love More Then %d\n", n); 
}

int main () {
    LoveYou(3000);
}

内层循环执行 $n^2$ 次，因此数量级为 $O(n^2)$

一些特别的情况

对于多层循环，我们只需要关注最深层次的代码语句的执行次数和时间规模 $n$ 的关系

对于某些循环次数与输入的变量大小有关时，一般会考虑最坏时间复杂度和平均时间复杂度

算法的空间复杂度

在程序运行时，会在内存中开辟一篇空间供程序本身的代码存储和变量使用，同样的分析上面的示例代码：

void LoveYou(int n) { // n 为问题规模
    int i; 
    while (i <= n) { 
        i++; 
        printf("I Love You %d\n", i); 
    }
    printf("I Love More Then %d\n", n); 
}

int main () {
    LoveYou(3000);
}

该算法在程序执行过程中只需要一个固定的代码空间和两个固定的变量空间 (两个int i) ，因此该算法的空间复杂度为常数即：

$$S(n) = O(1)$$

与时间复杂度相同，同样使用空间复杂度的数量级表示

一个需要注意的点，当一个算法的空间复杂度 $S(n)$ 与其问题规模 $n$ 之间没有关系，即算法空间复杂度为常量级 $S(n) = O(1)$ ，那么可以称该算法可以原地工作

对于下面的例子：

void test (int n) { // int n 占 4B
    int flag[n]; // flag 占 n * 4B
    int i;// i 占 4B
}

其所需要的空间为 $space = 4 + 4n + 4 = 8 + 4n$，同样的我们只需要关注数量级较高的那一项

因此最终的空间复杂度为 $O(n)$

对于数量级大小比较和加法乘法法则对于空间复杂度计算仍然有效

再贴一次大小排序

$$O(1) < O(\log_2n) < O(n) < O(n\log_2n) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)$$

递归调用中的空间复杂度分析

对于下面递归代码：

void test(int n) { // 问题规模 n
    int a, b, c; // 定义一系列变量
    // ...
    if ( n > 1 ) {
        test ( n - 1 );
    }
    printf("test %d\n", n); // 打印结果
}

int main() {
    test(5);
}

对于每一层调用，所需要的内存空间是固定的，即各种变量加上函数本身需要的固定占用，因此，对于问题规模 $n$ 对于每层所需固定内存占用 $k$ 的总空间复杂度为 $S(n) = O(n)$

对于下面的递归函数：

void test(int n) { // 问题规模 n
    int flag[n]; // 这里换成数组
    // ...
    if ( n > 1 ) {
        test ( n - 1 );
    }
    printf("test %d\n", n); // 打印结果
}

int main() {
    test(5);
}

对于这一种情况，则需要考虑每一次递归，函数中的数组所占的内存都不同，第 $x$ 次递归时数组需要的内存空间是 $(n - x) \times 4$ 直到 递归函数的参数为 1

根据分析，该算法空间复杂度为：

$$1 + 2 + 3 + \cdots + n = \frac{n(n + 1)}{2} = \frac{1}{2}n^2 + \frac{1}{2}n$$

明显可见，空间复杂度 $S(n) = O(n^2)$