算法

基本概念

• 算法：解决问题的方法和思想。
• 时间复杂度：算法执行时间与输入规模之间的关系。
• 空间复杂度：算法执行过程中使用的额外空间与输入规模之间的关系。
• 时间复杂度一般指最坏情况的时间复杂度。
• 大O记法：忽略常量因子，只描述量级和趋势，如：
  • O(1)：常数时间复杂度，不依赖输入规模。
  • O(log n)：对数时间复杂度。
  • O(n)：线性时间复杂度。
  • O(nlogn)：线性时间复杂度。
  • O(n^2)：平方时间复杂度。
  • O(n^3)：立方时间复杂度。
  • O(2^n)：指数时间复杂度。

排序

• 冒泡排序
  • 原理：比较相邻元素大小，每一轮将最大值移到末尾。
  • 复杂度：O(n^2)。
• 选择排序
  • 原理：每一轮选择一个最大与末尾交换。
  • 复杂度：O(n^2)。
• 插入排序
  • 原理：每一轮从未排序部分选择一个插入到已排序部分。
  • 复杂度：O(n^2)。
• 快速排序
  • 原理：将第一个元素作为基准值，不断左右交换直到左边都不比基准值大，右边不比基准值小。再同样方法二分处理左右子序。
  • 复杂度：O(nlogn)。
• 堆排序
  • 原理：不断构造最小堆，堆顶是最小值与最左边交换，再将堆大小减1。
  • 复杂度：O(nlogn)。
• 归并排序
  • 原理：分治法，分成两个序列分别排序再合并到一起。
  • 复杂度：O(nlogn)。
• 平均时间复杂度O(nlogn)：快堆归希
• 稳定排序：冒插归希

分治

• 思想：将问题划分成多个相同问题，再挨个解决。
• 举例：快速排序、二分查找。

贪心

• 思想：仅适用于局部最优能推出全局最优的问题，每次都选择局部最优直到解决问题。
• 举例：纸币最少张数找零。
  • 问题：纸币面值100、50、10、5、1，找任意数值如何做到最少张数？
  • 解决：从最大的钱开始找，逐步尝试小面额，直到找完为止。
• 举例：最小生成树。
  • 问题：连通无向图，每条边都有一个权值，如何找到最小生成树？
  • 解决：每次选择与当前树相连的最小权值的边，直到所有节点都连通为止。
• 举例：背包问题
  • 问题：背包有限容量，物品有重量和价值，如何选择物品装入背包以达到最大价值。
  • 解决：每次选择单位价值最大的物品，直到装满。

回溯

• 思想：是一种搜索算法，如果可以往前则往前，否则回溯。
• 举例：迷宫
  • 问题：给定一个迷宫，如何找到从起点到终点的最短路径？
  • 解决：回溯法可以找到所有可行解，从而寻找最优。

动态规划

• 思想：适用于解决具有最优子结构的问题，这类问题往往需要重复解决很多相同的最优解子问题，需要把子问题的结果保存起来避免重复计算。
• 贪心法的局部最优可能不是全局最优，而动态规划法可以保证找到全局最优。
• 举例：斐波那契数列
  • 问题：求斐波那契数列的第n项？
  • 解决：递归法会重复计算，而动态规划法可以避免重复计算。