Skip to main content

第23章 算法与算法描述

算法是程序设计的核心，是解决特定问题的一系列清晰、可执行的指令集合，程序本质是算法的代码实现。

23.1 算法的概念​

算法：解决特定问题、有限步可执行的步骤集合，拥有明确输入输出，能在有限时间完成求解。

23.2 算法五大基本特性​

  1. 有穷性：算法执行步骤一定有限，不能无限循环死循环。 例：循环计算1~100求和，最多100次循环后结束。
  2. 确定性：每一步定义无歧义，相同输入必然得到相同输出。 模糊描述“随便算一下”不满足确定性。
  3. 可行性：每一步都能用基础操作在有限时间完成。 无法实现无限小数精确求值，不具备可行性。
  4. 输入：0个或多个外部输入数据，代表问题初始状态。 求最大值需要输入两个数字；打印Hello无需输入。
  5. 输出：至少一个结果，反映问题答案。排序算法输出有序数组。

23.3 算法四大评价标准​

  1. 正确性：所有合法输入都能算出正确结果，最基础要求。
  2. 可读性：逻辑清晰易懂，方便调试、修改维护。
  3. 时间复杂度：衡量运行快慢，用大O记号 O(...)O(...) ，数值越小效率越高。 O(n)O(n) 远快于 O(n2)O(n^2)。
  4. 空间复杂度：运行额外占用内存大小，资源受限场景重点考量。

23.4 四种算法描述方法​

23.4.1 自然语言（中文/英文）​

优点：通俗易懂；缺点：冗长、容易产生歧义。 示例：求两数最大值

  1. 输入整数a、b；
  2. 比较a和b；
  3. 若a>b输出a，否则输出b。

23.4.2 流程图​

标准图形符号：

  • 圆角矩形：开始、结束
  • 矩形：处理计算步骤
  • 菱形：条件判断分支
  • 箭头：执行流向

23.4.3 伪代码​

介于自然语言与代码之间，忽略编程语言语法，只保留逻辑，极易转成C/C++代码。 示例：选择排序伪代码

算法：选择排序
输入：长度n数组arr
1. i从0到n-2循环
    min_index = i
    j从i+1到n-1循环
        若arr[j]<arr[min_index]，更新min_index=j
    交换arr[i]与arr[min_index]
2. 输出数组arr

23.4.4 编程语言（C/C++）​

直接可运行完整代码，语法严格无歧义。 示例：欧几里得求最大公因数，再计算最小公倍数

#include<iostream>
using namespace std;
int main()
{
    int num1, num2;
    cout << "请输入两个整数：";
    cin >> num1;
    int a = num1, b = num2;
    // 辗转相除法求gcd
    while(b != 0)
    {
        int temp = b;
        b = a % b;
        a = temp;
    }
    int gcd = a;
    int lcm = (num1 * num2) / gcd;
    cout << "最大公约数：" << gcd << endl;
    cout << "最小公倍数：" << lcm << endl;
    return 0;
}

23.5 常见基础算法思想​

  1. 枚举：遍历全部候选解，筛选符合条件答案；例：百钱百鸡、水仙花数。
  2. 递推：已知初始值，按公式向后迭代；例：斐波那契、阶乘。
  3. 递归：大问题拆分成同结构小问题，自身调用；例：阶乘、汉诺塔。
  4. 贪心：每一步取局部最优，期望全局最优；例：活动选择。
  5. 分治：均分拆分子问题，分别求解后合并；例：快速排序、归并排序。