Docker笔记

复杂度

计算时间复杂度的方法

数循环次数：循环的嵌套

均摊分析：(1+n)/2，一次性的操作平均到整体

递归式:主定理

常见的时间复杂度

1:基本运算，+,-,*,/,%,寻址

logn：二分查找

根号n:枚举约数，少见

n:线性查找，很多时候算法的下限就是n，因为数据的读入的复杂度就已经是n了

nlogn：归并排序，快速排序的期望复杂度，基于比较排序的算法下界

---

n的平方：朴素最近点对，冒泡排序，选择排序

n的三次方：Floyd最短路径，普通矩阵乘法

2的n次方：枚举全部的子集

n的阶乘：枚举全排列

排序算法

搜索算法