算法学习笔记一、时空复杂度

面试求职班一笔记

1. 算法主要研究：时空复杂度

2. 算法的特征：

    1. 有穷性，
    2. 确定性，
    3. 可行性，
    4. 可能没有输入，但一定有输出
   

3. 常用算法

    1. 穷举法（eg：求N个数的全排列；8皇后问题）
    2. 减而治之（二分查找——减而治之；归并排序——分而治之）
    3. 贪心算法（最小生成树；单源最短路）所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。
    4. 动态规划（背包；士兵路径）
   

4. 复杂度

    1. 谈算法一定要考虑复杂度
    2. 时间复杂度和空间复杂度
    	1. 时间复杂度：计算机基本操作的次数（汇编指令的条数）+ - * / % 寻址 跳转
    	2. 空间复杂度：所需占用的内存字节数
    	3. 两者区别：空间是可以返回利用的。
    	4. 表示方法：O(n) 忽略常数（高阶无穷小）注意：算法复杂度是考虑算法最坏情况时的复杂度
    	5. eg: 快速排序的复杂度 O(n^2)，这个就是他的最坏情况
    3. 常见的复杂度
    	1. O(1): 基本运算 + - * / % 寻址  跳转
    	2. O(logN): 二分查找
    	3. O(N^(1/2)): 枚举约数
    	4. O(N): 线性查找
    	5. O(N^2): 朴素最近带你对
    	6. O(N^3): Floyd最短路；普通矩阵乘法
    	7. O(NlogN): 归并排序；快速排序的期望复杂度；基于比较排序的算法下界
   

$$a_1,a_2,...a_n 排序全排列的时间复杂度为 n!$$
$$ 当 a_i< a_j时$$
$$复杂度变为: \frac{n!}{2}$$
$$当有k个关系时，每次都能排除一般的可能$$
$$复杂度为: \frac{n!}{2^k}$$
$$令: \frac{n!}{2^k} = 1 即 n!=2^k$$
$$k=\log_{2}{n!} < \log_{2}{n^n}=n\log_{2}{n}=n\frac{\log n}{\log2}< n\log{n}$$
以上为推导过程

		8. O($2^N$): 枚举全部的子集   注意：一个集合全部子集的数量是2^N
		9. O($N!$): 枚举全部排列

总结:

• 优秀算法排序：
  $$O(1) < O(\log{n}) < O(\sqrt{n} < O(n) < O(n\log{n}))$$

• 可以优化的：
  $$O(n^2)< O(n^3)< O(2^n)< O(n!)$$

• 算法估计，计算机1s能运算1亿条指令，注意以下数字
  $$(1000)^2=1亿; (465)^3=100,544,625; 12!=479001600$$

###常用的时间复杂度分析方法
1. 输入输出
1. N个数组求和，时间复杂度下限为: O(n)
2. 输出全排列的复杂度在O(n!)以上
2. 循环次数
eg: 循环嵌套的复杂度至少是O(n^2)
for(i...n)
for(i...n)

	3. 均摊分析法
		多个操作一起计算时间复杂度
		eg1: MULTIPOP的队列，可以一次性出队k个元素，但每个元素出入队列只能有一次
		eg2: 动态数据尾部插入操作（C++中是vector，java中是ArrayList）
		一旦元素超过容量限制，则重新扩大并分配空间，将旧数据复制到新的内存地址上。
		有空间的情况下复杂度是O(1)
		空间满了再扩大的时候的复杂度是O(n)
		重新分配k次的复杂度是O(2^n)

$$O(1)+O(2)+O(4)+...+O(2^n)=O(2^n-1)$$