算法分析与设计

基本概念

算法的基本概念

算法：一个专门为解决某一问题的有穷指令集合特点：

有穷性
可行性
确定性
输入
输出

相较于算法，程序可以不用满足有穷性，例如操作系统是一个程序，但不满足有穷性

可计算性与计算复杂性

对于一个问题，根据是否能确定能在多项式时间内（例如时间复杂度为O(n^100)，而不是O(2^n)）用图灵机解决一个决策问题，来划分是P问题还是NP问题

P 问题：解决这个问题的事件随着规模n是多项式增长的，即这个问题可以在多项式时间内被图灵机解决，例如O(n^2)。
NP 问题是那些我们很难在多项式时间内直接找到解，但能在多项式时间内验证一个给定的解是否正确的问题。

算法时间复杂性

算法时间复杂性：算法中元运算的执行次数为输出，其问题规模为输入的函数元运算：这个算法中最小的时间常量，例如基本算数运算，逻辑运算，赋值运算

大O符号 (O) - 时间复杂度的“最坏情况保证”: O 符号的数学定义，它如何描述函数增长率的上限。
大Ω符号 (Ω) - 时间复杂度的“最好情况保证”: Ω 符号的数学定义，它如何描述函数增长率的下限。
大Θ符号 (Θ) - 时间复杂度的“精确估计”:
- 严肃严谨地讲：Θ 符号的数学定义，以及它与 O 和 Ω 的关系（当上界和下界相同时）。

具体如何计算时间复杂度：

确定元运算
顺序结构各部分时间相加
if else取时间最大的部分
for while循环中循环次数* 内部操作时间
函数调用/递归算法

常见的时间复杂度例子 O(n^2)

function printPattern(n) {
  console.log("Pattern:");
  let totalOperations = 0;
  for (let i = 0; i < n; i++) {       // 外层循环
    for (let j = 0; j < i; j++) {   // 内层循环，注意 j < i
      console.log("i: " + i + ", j: " + j);
      totalOperations++;
    }
  }
  console.log("Total operations for pattern: " + totalOperations);
  return totalOperations;
}

O(log2(n))

function analyzeThisLoop(n) {
  let operations = 0;
  for (let i = 1; i < n; i = i * 2) {
    // 假设这里有一些 O(1) 的操作
    console.log("Current i: " + i);
    operations++;
  }
  console.log("Total operations: " + operations);
  return operations;
}
 
// 假设 n 是一个正整数，例如：
// analyzeThisLoop(100);

Pasted image 20250701214818

归纳法

归纳法是一种推理方法，它的特点是从个别的、具体的事实或观察中，推导出普遍的、一般性的结论。这种推理过程是从“特例”到“一般”的过程。

特点：

不保证绝对正确性：归纳法的结论仅仅是“很可能”，“高度可能”
新知识的来源：尽管有局限性，但这个是我们获取新知识的来源

递归算法

递归算法 是一种解决问题的方法，它通过将问题分解成更小的、相同类型的问题来解决。它通常包含两个部分：

递归关系：算法中的某个步骤要通过解决性质相同的子问题的时候，这个子问题与父问题就是递归关系
递归出口：当子问题分解的规模足够小，可以直接求解的时候，就让递归结束

几个递归算法的示例：

冒泡排序选择排序插入排序整数幂问题棋子移动游戏全排列问题寻找多数元素

分治算法

分治算法的基本思想是：将一个大问题，分解为多个和大问题性质相同的小问题（递归）来进行解决。

分治算法的一般步骤：

分解
直接/递归求解子问题
组合子问题的答案

几个分治算法示例：

归并排序快速排序大整数乘法寻找第k小元素

动态规划算法

动态规划算法在分治算法的过程当中，分为若干个子问题有时候是完全相同的，我们只需要把它存储起来，用到的时候在查找提取，可以大大优化算法的时间复杂度

矩阵链乘问题最长公共子序列 0 1背包问题

嵌套矩阵问题最优搜索树问题

贪心算法

贪心算法的基本思想是在问题的每个决策阶段，贪心的选择当前局部的最优解，以期望获得全局最优。

贪心算法和动态规划都常用于解决优化问题。它们之间存在一些相似之处，比如都依赖最优子结构性质，但工作原理不同。

动态规划会根据之前阶段的所有决策来考虑当前决策，并使用过去子问题的解来构建当前子问题的解。
贪心算法不会考虑过去的决策，而是一路向前地进行贪心选择，不断缩小问题范围，直至问题被解决

分数背包问题多机调度问题

有期限的作业安排问题（普利姆）Prim算法哈夫曼树（最小生成树）

回溯算法

回溯算法是一种通过穷举来解决问题的方法，它的核心思想是从一个初始状态出发，暴力搜索所有可能的解决方案，当遇到正确的解则将其记录，直到找到解或者尝试了所有可能的选择都无法找到解为止

全排列问题图的着色问题 n皇后问题

哈密顿回路问题迷宫问题子集和问题八数码问题

探索

Akiyama's blog

算法分析与设计 - INDEX