一、什么是O，时间复杂度
1、概念
n表示数据规模
O(f(n)) 表示运行算法所需要的执行的指令数，和f(n) 成正比。
O(nlogn + n) = O(nlogn)
但，O(AlogA +B) 中AB不能互相替换，AB不是一个问题规模，如：邻接表实现对图的遍历 O(V + E)几个常用算法时间复杂度：
二分查找发O(logn) 所需执行指令数：alogn
寻找数组中的最大/小值 O(n) 所需执行指令数：bn
归并排序酸法O(nlogn) 所需执行指令数：cnlogn
选择排序算法O(n^2) 所需执行指令数：dn^2
变化趋势
二、数据规模n
1、数据规模：运行时间
10^8：0.4秒
10^9：4秒
如果想要在1s内解决问题：
- O(n^2) 的算法可以处理大约10^4级别的数据（一次操作）
- O(n) 的算法可以处理大约10^8级别的数据
- O(nlogn) 的算法可以处理大约10^7级别的数据
2、空间复杂度
- 多开一个辅助的数组：O(n)
- 多开一个辅助的二维数组：O(n^2)
- 多开常数空间：O(1)
- 递归调用是有空间代价的，递归的深度即是多的空间。
三、例子
1、例题
有一个字符串数组，将数组中的每一个字符串按照字母序排序；之后在将整个字符串数组按照字典序排序。整个操作的时间复杂度？
分析：
假设最长字符串长度S；数组中有n个字符串。
对每个字符串排序：O(slogs)
将字符串数组中n个字符串排序：O(snlogn)
整体：O(nslogs) + O(snlogn) = O(nslogs + snlogn) = O(ns*(logs+logn))
- 排序中比较的次数的复杂度为 O(nlogn)，即整型时排序的时间复杂度。
- 两个字符串（长s）进行比较，还需比较两个字符串的字典序，即需要时间复杂度 O(s)。
- 算法复杂度在有些情况是与用例相关的
2、二分查找法
二分查找法
二分查找法分析
3、int转string——O(logn)
int转string
- O(logaN) = O(logbN) =O(logN) 底省略
4、注意循环条件——O(logn)
O(nlogn)
5、判断是否是素数——O(sqrt(n))
找素数O(sqrt(n))
6、归并排序——O(nlogn)
归并排序O(nlogn)
四、复杂度实验
通过让数据规模n*2，看时间增长趋势
O(n^2)的话，数据扩大2倍，时间扩大4倍。
实验
结果
五、递归算法分析
- 不是有递归的函数就一定是O(nlogn)
1、递归中进行一次递归调用
计算递归调用的深度，
二分查找法
方法
x^n改进算法，正常是O(n)
2、多次递归调用
- 画递归树，数所有树上的节点
- 2^(n+1) -1 = O(2^n) 指数级算法，非常慢
两次递归，深度为n
-
分治算法
归并排序O(nlogn)
问题：为什么归并排序不是O(2^n)，而是O(nlogn)？
答：因为之前的例子中整棵树的深度为n，在排序搜索中树的深度是logn；之前每个节点处理数据规模是一样的，排序搜索中处理每层数据规模是n，即n*logn。 - 主定理——归纳了递归函数的时间复杂度。
六、均摊复杂度分析
1、动态数组（Vector） 动态栈、动态队列
动态数组push_back函数
push_back时间复杂度分析
push_back时间复杂度：O(1)
2、避免复杂度震荡
image.png
image.png
image.png
测试
动态数组实现：
public class MyVector<Item> {
private Item[] data;
private int size; // 存储数组中的元素个数
private int capacity; // 存储数组中可以容纳的最大的元素个数
public MyVector(){
data = (Item[])new Object[100];
size = 0;
capacity = 100;
}
// 添加元素——平均复杂度为 O(1)
public void push_back(Item e){
if(size == capacity)
resize(2 * capacity);
data[size++] = e;
}
// 删除元素，输出pop出的元素ret——平均复杂度为 O(1)
// 并不是真正的删除，通过调整size来动态改变数组
public Item pop_back(){
if(size <= 0)
throw new IllegalArgumentException("can not pop back for empty vector.");
Item ret = data[size-1];
size --;
// 在size达到静态数组最大容量的1/4时才进行resize
// resize的容量是当前最大容量的1/2
// 防止复杂度的震荡
if(size == capacity / 4)
resize(capacity / 2);
return ret;
}
// 复杂度为 O(n)
private void resize(int newCapacity){
assert newCapacity >= size;
Item[] newData = (Item[])new Object[newCapacity];
// 把data中的元素，存到newData数组中
for(int i = 0 ; i < size ; i ++)
newData[i] = data[i];
// 将修改容量后的数组赋给data
data = newData;
capacity = newCapacity;
}
// 注意：Java语言由于JVM内部机制的因素，测量的性能时间有可能是跳跃不稳定的。
public static void main(String[] args) {
for( int i = 10 ; i <= 26 ; i ++ ){
int n = (int)Math.pow(2,i);
long startTime = System.currentTimeMillis();
MyVector<Integer> vec = new MyVector<Integer>();
for(int num = 0 ; num < n ; num ++){
vec.push_back(num);
}
for(int num = 0 ; num < n ; num ++){
vec.pop_back();
}
long endTime = System.currentTimeMillis();
System.out.print(2 * n + " operations: \t");
System.out.println((endTime - startTime) + " ms");
}
}
}
ps：截图代码C++，代码段java
