Cliff_Ford-算法总纲

如果觉得Cliff_Ford写得不错，点赞鼓励下吧！总纲会不断的变化，持续更新完善

什么是算法

算法是计算或者解决问题的有限步骤，针对规范输入，给出确却的运行结果。

如何衡量算法的好坏

我们通常关注算法的时间复杂度和空间复杂度，权求得一种两者相对平衡的方案，但更多的是用空间换取时间。

算法运行时间的估算

假设现在通过选择排序的方式将n个数从小到大排序，运行时间的估算方法如下：

• 设比较两个数大小所花费的时间为C，交换两个数的位置所花费的时间为S
• 一轮比较确定一个最小的数，且下一轮总比上一轮少比较一次
• 第一轮确定并交换两个数的位置所花费的时间为 nC+S
• 第二轮确定并交换两个数的位置所花费的时间为 (n-1)C+S
• 最后一轮时间为 C+S
• 总时间为
• 聚焦于总时间的最重要项 n
• 记选择排序的时间复杂度为 O(n^2)

常见的排序算法及其时间复杂度如下表

注：图片来自菜鸟教程

时间复杂度由小到大排序如下

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n)
算法的好坏通常也由时间复杂度评定

承载算法的数据结构

注：这都是一些超链接，我会一个个将其完善

• 数组
• 链表
• 栈
• 队列
• 散列表
• 树
• 堆
• 图

算法分类（按功能）

• 排序算法
• 查找算法
• 安全算法
• 聚类算法
• 图论算法
• 其他算法

算法分类（按招式）

• 递推法
• 递归法
• 穷举法
• 贪心法
• 分治法
• 动态规划法
• 迭代法
• 分支界限法
• 回溯法