数据结构和算法：复杂度分析

算法效率评估

时间效率：算法运行速度的快慢。
空间效率：算法占用内存空间的大小。

效率评估方法主要分为两种：实际测试、理论估算

实际测试问题：
1.难以排除测试环境的干扰因素。
硬件配置会影响算法的性能。需要在各种机器上进行测试，统计平均效率，而这是不现实的。
2.展开完整测试非常耗费资源。
随着输入数据量的变化，算法会表现出不同的效率。因此，为了得到有说服力的结论，需要测试各种规模的输入数据，而这需要耗费大量的计算资源。

由于实际测试具有较大的局限性，因此我们可以考虑仅通过一些计算来评估算法的效率。这种估算方法被称为渐近复杂度分析 （asymptotic complexity analysis），简称复杂度分析。

复杂度分析能够体现算法运行所需的时间和空间资源与输入数据大小之间的关系。它描述了随着输入数据大小的增加，算法执行所需时间和空间的增长趋势。
1.“时间和空间资源”分别对应时间复杂度（time complexity）和空间复杂度（space complexity）。
2.“随着输入数据大小的增加”意味着复杂度反映了算法运行效率与输入数据体量之间的关系。
3.“时间和空间的增长趋势”表示复杂度分析关注的 不是运行时间或占用空间的具体值，而是时间或空间增长的“快慢”。

复杂度分析克服了实际测试方法的弊端：
1.独立于测试环境，分析结果适用于所有运行平台；
2.可以体现不同数据量下的算法效率，尤其是在大数据量下的算法性能。

迭代与递归

迭代（iteration） 是一种重复执行某个任务的控制结构。在迭代中，程序会在满足一定的条件下重复执行某段代码，直到这个条件不再满足。

/**
 * File: iteration.cpp
 * Created Time: 2023-08-24
 * Author: Krahets (krahets@163.com)
 */

#include "../utils/common.hpp"

/* for 循环 */
int forLoop(int n) {
    int res = 0;
    // 循环求和 1, 2, ..., n-1, n
    for (int i = 1; i <= n; ++i) {
        res += i;
    }
    return res;
}

/* while 循环 */
int whileLoop(int n) {
    int res = 0;
    int i = 1; // 初始化条件变量
    // 循环求和 1, 2, ..., n-1, n
    while (i <= n) {
        res += i;
        i++; // 更新条件变量
    }
    return res;
}

/* while 循环（两次更新） */
int whileLoopII(int n) {
    int res = 0;
    int i = 1; // 初始化条件变量
    // 循环求和 1, 4, 10, ...
    while (i <= n) {
        res += i;
        // 更新条件变量
        i++;
        i *= 2;
    }
    return res;
}

/* 双层 for 循环 */
string nestedForLoop(int n) {
    ostringstream res;
    // 循环 i = 1, 2, ..., n-1, n
    for (int i = 1; i <= n; ++i) {
        // 循环 j = 1, 2, ..., n-1, n
        for (int j = 1; j <= n; ++j) {
            res << "(" << i << ", " << j << "), ";
        }
    }
    return res.str();
}

/* Driver Code */
int main() {
    int n = 5;
    int res;

    res = forLoop(n);
    cout << "\nfor 循环的求和结果 res = " << res << endl;

    res = whileLoop(n);
    cout << "\nwhile 循环的求和结果 res = " << res << endl;

    res = whileLoopII(n);
    cout << "\nwhile 循环（两次更新）求和结果 res = " << res << endl;

    string resStr = nestedForLoop(n);
    cout << "\n双层 for 循环的遍历结果 " << resStr << endl;

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

递归 （recursion） 是一种算法策略，通过函数调用自身来解决问题。它主要包含两个阶段：
1.递：程序不断深入地调用自身，通常传入更小或更简化的参数，直到达到“终止条件”。
2.归：触发“终止条件”后，程序从最深层的递归函数开始逐层返回，汇聚每一层的结果。

/**
 * File: recursion.cpp
 * Created Time: 2023-08-24
 * Author: Krahets (krahets@163.com)
 */

#include "../utils/common.hpp"

/* 递归 */
int recur(int n) {
    // 终止条件
    if (n == 1)
        return 1;
    // 递：递归调用
    int res = recur(n - 1);
    // 归：返回结果
    return n + res;
}

/* 使用迭代模拟递归 */
int forLoopRecur(int n) {
    // 使用一个显式的栈来模拟系统调用栈
    stack<int> stack;
    int res = 0;
    // 递：递归调用
    for (int i = n; i > 0; i--) {
        // 通过“入栈操作”模拟“递”
        stack.push(i);
    }
    // 归：返回结果
    while (!stack.empty()) {
        // 通过“出栈操作”模拟“归”
        res += stack.top();
        stack.pop();
    }
    // res = 1+2+3+...+n
    return res;
}

/* 尾递归 */
int tailRecur(int n, int res) {
    // 终止条件
    if (n == 0)
        return res;
    // 尾递归调用
    return tailRecur(n - 1, res + n);
}

/* 斐波那契数列：递归 */
int fib(int n) {
    // 终止条件 f(1) = 0, f(2) = 1
    if (n == 1 || n == 2)
        return n - 1;
    // 递归调用 f(n) = f(n-1) + f(n-2)
    int res = fib(n - 1) + fib(n - 2);
    // 返回结果 f(n)
    return res;
}

/* Driver Code */
int main() {
    int n = 5;
    int res;

    res = recur(n);
    cout << "\n递归函数的求和结果 res = " << res << endl;

    res = forLoopRecur(n);
    cout << "\n使用迭代模拟递归求和结果 res = " << res << endl;

    res = tailRecur(n, 0);
    cout << "\n尾递归函数的求和结果 res = " << res << endl;

    res = fib(n);
    cout << "\n斐波那契数列的第 " << n << " 项为 " << res << endl;

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

递归：1+2+…+n

/* 递归 */
int recur(int n) {
    // 终止条件
    if (n == 1)
        return 1;
    // 递：递归调用
    int res = recur(n - 1);
    // 归：返回结果
    return n + res;
}
1
2
3
4
5
6
7
8
9
10

调用栈

递归函数每次调用自身时，系统都会为新开启的函数分配内存，以存储局部变量、调用地址和其他信息等。
这将导致两方面的结果：
1.函数的上下文数据都存储在称为“栈帧空间”的内存区域中，直至函数返回后才会被释放。因此，递归通常比迭代更加耗费内存空间。
2.递归调用函数会产生额外的开销。因此递归通常比循环的时间效率更低。

栈顺序：先入后出

尾递归

如果函数在返回前的最后一步才进行递归调用，则该函数可以被编译器或解释器优化，使其在空间效率上与迭代相当。这种情况被称为尾递归 （tail recursion）。

许多编译器或解释器并不支持尾递归优化，如 Python，即使函数是尾递归形式，仍然可能会遇到栈溢出问题。

普通递归：当函数返回到上一层级的函数后，需要继续执行代码，因此系统需要保存上一层调用的上下文。
尾递归：递归调用是函数返回前的最后一个操作，这意味着函数返回到上一层级后，无须继续执行其他操作，因此系统无须保存上一层函数的上下文。

/* 尾递归 */
int tailRecur(int n, int res) {
    // 终止条件
    if (n == 0)
        return res;
    // 尾递归调用
    return tailRecur(n - 1, res + n);
}
1
2
3
4
5
6
7
8

普通递归：求和操作是在“归”的过程中执行的，每层返回后都要再执行一次求和操作。
尾递归：求和操作是在“递”的过程中执行的，“归”的过程只需层层返回。

递归树

给定一个斐波那契数列 0, 1, 1, 2, 3, 5, 8, 13, … ，求该数列的第