1、热身：从一个数组查找一个数，需要花多少时间？假如数组长度10个？假如数组长度1万个？假如数组长度100万个？
-
最好的情况：第一个 T(n)=O(1) - 最坏的情况：最后一个 T(n)=O(n) - 期望情况(平均情况)：T(n)=O(n)
-
时间复杂度： 执行算法所需要的计算工作量
-
空间复杂度： 执行算法所需要的内存空间
2、什么是时间复杂度
- 在计算机科学中，时间复杂性，又称时间复杂度，算法的时间复杂度是一个函数，它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。
3、时间复杂度计算-一般问题
- 基本操作的时间复杂度：丢弃常数项、丢弃次要项
- 复合操作：加还是乘
4、时间复杂度计算-递归问题
-
什么是递归：在数学与计算机科学中，是指在函数的定义中使用函数自身的方法。递归一词还较常用于描述以自相似方法重复事物的过程。
-
经验性结论：递归问题的时间复杂度通常(并不总是)看起来形如O(branchesdepth)，其中branches指递归分支的总数，depth指递归调用深度
5、时间复杂度计算-主定理
6、计算例题
- 该题的空间复杂度为 O(2n) –> O (n)
void foo(int[] array){
int sum = 0;
int product = 1;
for(int i =0; i < array.length; i++){
sum += array[i]
}
for(int i =0; i < array.length; i++){
product *= product[i]
}
System.out.println(sum + "," + product)
}
- 该题的空间复杂度为 O(n2)
void printPairs(int[] array){
for(int i = 0; i < array.length; i++){
for(int j = 0;j < array.length; j++){
System.out.println(array[i]+ "," + array[j])
}
}
}
- 该题的空间复杂度为 O(n2*100000+n) –> O(n2 )
void foo(int[] arrayA, int[] arrayB) {
for (int i = 0; i < arrayA.length; i++) {
for (int j = 0; j < arrayB.length; j++) {
for (int k = 0; k < 100000; k++) {
System.out.println(arrayA[i] + "," + arrayB[j]);
}
}
}
}
- 递归时间复杂度 O(2log2n) -> O(n),分支为2，深度为log2n。注意这题和下题的区别
int sum(Node node){
if(node === null){
return 0;
}
return sum(node.left)+node.value+sum(node.right)
}
- 递归时间复杂度为O(2n),分支为2，深度为n
int calculate(int n){
if(n<=0){
return 1;
}
return calculate(n-1) + calculate(n-1)
}
假如n=4
第0个节点 调用1次函数 calculate(4)
第1个节点 调用2次函数 calculate(3)
第2个节点 调用4次函数 calculate(2)
第3个节点 调用8次函数 calculate(1)
第4个节点 调用16次函数 calculate(0)
所以规律是：
第n个节点 调用2^n次函数 calculate(0)
2^0 + 2^1 + …… + 2^n = O(n^2)
- 斐波那契数列递归时间复杂度 O(2n),分支为2，深度计算为n。注意这种没有优化的递归，性能不怎么好
void fib(int n) {
if(n <= 0) return 1;
else if(n==1) return 1;
return fib(n-1) + fib(n-2)
}