算法复杂度与迭代递归篇2

算法复杂度与迭代递归篇2

引用

CSDN

1.

https://blog.csdn.net/weixin_44262492/article/details/145146503

前言

本文主要介绍算法效率评估的两个方面：实际测试与理论估算，以及通过渐近复杂度分析来评估算法的时间和空间效率。

1、算法效率目标

• ①找到问题解法：需要在规定输入范围内可靠地解决问题。
• ②寻求最优解法：即使问题解决，算法效率仍然是衡量其优劣重要标准。找到高效算法在有限的时间和空间内解决问题。
• ③算法效率的评估包括：
• 时间效率：算法运行所需时间长短。
• 空间效率：算法占用内存空间大小。
  总体目标：“既快又省”算法和数据结构。

2、效率评估方法

主要有两种方式：实际测试与理论估算。

2.1、实际测试

• 对比算法 A 和 B：在同一台计算机上运行两个算法，记录运行时间和内存使用情况，直观地对比效率。
• 局限性：
• 硬件环境的影响：测试结果受到硬件配置影响。某些算法在多核 CPU 上更高效，而另一些则可能依赖于更强内存操作能力。
• 测试环境不一致：算法表现可能在不同的机器或环境中有所不同，因此，进行广泛测试以获得全面的结果不现实。
• 资源消耗：随着输入数据量增加，算法效率变化会更加明显，需要进行大量测试，耗费大量资源。
  由于这些局限性，实际测试并不是一种理想效率评估方式。

2.2、理论估算（渐近复杂度分析）

渐近复杂度分析（Asymptotic Complexity Analysis），简称复杂度分析，是评估算法效率的一种更为理想方式。

• 核心思想：
• 复杂度分析关注是时间和空间资源（时间复杂度与空间复杂度）与输入数据大小之间关系，特别是在数据量很大情况下的算法性能表现。
• 时间复杂度（Time Complexity）：算法执行所需时间资源。
• 空间复杂度（Space Complexity）：算法占用内存空间。
• 增长趋势：分析重点不是算法具体运行时间或占用空间，而是它们如何随着输入数据量增加而增长。通过对比不同算法复杂度，了解在不同数据量下表现差异。
• 复杂度分析的优点：
• 不需要实际运行代码，节省资源。
• 独立于测试环境，分析结果适用于所有平台。
• 在理论上估算算法在大数据量下的表现，避免实际测试中局限性。
• 难度与挑战：复杂度分析是一个数学概念，初学者可能会觉得抽象，学习难度较高。尤其是理解大O符号、渐进时间复杂度等概念时可能会感到困难，在数据结构与算法分析中非常重要。

2.3、总结

• 评估算法效率：方法有实际测试和理论估算两种，但理论估算（即复杂度分析）更加高效且适用范围更广。
• 复杂度分析：提供衡量和对比算法效率标准，能够在没有运行算法情况下，预测在大数据量下表现。
  PS：
• 初学者在深入学习数据结构与算法时，应对复杂度分析有一定了解，以便在后续学习中能够进行简单复杂度分析和算法优化。

3、迭代与递归

在算法中，重复执行某个任务很常见，它与复杂度分析息息相关。在介绍时间复杂度和空间复杂度之前，先了解如何在程序中实现重复执行任务，两种基本的程序控制结构：迭代、递归。

虽然从计算角度看，迭代与递归得到相同结果，代表两种完全不同思考和解决问题范式。

• 迭代：“自下而上”地解决问题。从最基础步骤开始，然后不断重复或累加这些步骤，直到任务完成。
• 递归：“自上而下”地解决问题。将原问题分解为更小子问题，这些子问题和原问题具有相同形式。接下来将子问题继续分解为更小子问题，直到基本情况时停止（基本情况解已知）。

3.1、迭代

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

3.1.1、for 循环

for 循环是最常见迭代形式之一，适合在预先知道迭代次数时使用。

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

流程图如下：

3.1.2、while 循环

与 for 循环类似，while 循环是一种实现迭代方法。在 while 循环中，程序每轮都会先检查条件，如果条件为真，则继续执行，否则就结束循环。

/* 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 循环比for循环的自由度更高。在 while 循环中，自由地设计条件变量的初始化和更新步骤。例如在以下代码中，条件变量i每轮进行两次更新，这种情况就不太方便用 for 循环实现：

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

3.1.3、嵌套循环

在一个循环结构内嵌套另一个循环结构，以 for 循环为例：

/* 双层 for 循环 */
String nestedForLoop(int n) {
    StringBuilder res = new StringBuilder();
    // 循环 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.append("(" + i + ", " + j + "), ");
        }
    }
    return res.toString();
}

在这种情况下，函数操作数量与成正比，或者说算法运行时间和输入数据大小 成“平方关系”。继续添加嵌套循环，每一次嵌套都是一次“升维”，将会使时间复杂度提高至“立方关系”“四次方关系”，以此类推。

3.2、递归

递归（recursion）是一种算法策略，通过函数调用自身来解决问题。它主要包含两个阶段。

• 递：程序不断深入地调用自身，通常传入更小或更简化的参数，直到达到“终止条件”。
• 归：触发“终止条件”后，程序从最深层递归函数开始逐层返回，汇聚每一层结果。

而从实现的角度看，递归代码主要包含三个要素。

• 终止条件：决定什么时候由“递”转“归”。
• 递归调用：对应“递”，函数调用自身，通常输入更小或更简化参数。
• 返回结果：对应“归”，将当前递归层级的结果返回至上一层。

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

3.2.1、调用栈

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

3.2.2、递归树

当处理与“分治”相关算法问题时，递归往往比迭代思路更加直观、代码更加易读。以“斐波那契数列”为例。

/* 斐波那契数列：递归 */
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;
}

观察以上代码，在函数内递归调用两个函数，从一个调用产生两个调用分支。不断递归调用下去，最终将产生一棵层数为 n的递归树

• 本质上：递归体现“将问题分解为更小子问题”的思维范式，分治策略至关重要。
• 算法角度：搜索、排序、回溯、分治、动态规划等许多重要算法策略直接或间接地应用该思维方式。
• 数据结构角度：递归天然适合处理链表、树和图的相关问题，适合用分治思想进行分析。