对算法的思考

背景

在LeetCode上刷了上百道算法后，有了一些自己对于算法思路上的个人总结，这些总结偏向个人化，不一定适合每个人，写下来方便自己以后回顾，此为背景。本篇文章将以便条形式，碎片化更新。

算法中的数学方法

• 数学归纳法（例如：全排列）

查找排序

• 归并排序
  • 时间复杂度O(nlogn)，空间复杂度O(n)，稳定
  • 核心思想
    • 分解：将当前待排序的序列分成两个等长的子序列，直到子序列的长度为1。
    • 递归：对两个子序列递归地执行归并排序，直到子序列的长度为1，此时可以认为子序列已经是有序的（因为只包含一个元素）。
    • 合并：将两个有序的子序列合并成一个有序序列。合并过程中，比较两个子序列的当前元素，将较小的元素放入新的序列中，直到其中一个子序列的所有元素都被放入新的序列中，然后将另一个子序列中剩余的元素直接放入新的序列的末尾。
• 滑动窗口
• 动态规划
  • 通常用于解决最优化问题，其中子问题的解被保存和重用以避免重复计算
  • 贪心算法：动态规划的一种，核心是通过局部最优解得到整体最优解