算法-时间复杂度和空间复杂度

Big O notation

O(1):Constant Complexity 常数复杂度
O(log n):Logarithmic Complexity 对数复杂度
O(n):Liner Complexity 线性时间复杂度
O(n^2):N square Complexity平方
O(n^3):N cubic Complexity立方
O(2^n):Exponential Growth指数
O(n!):Factorial阶乘
注意:只看最高复杂度的运算

O(1)

int n = 1000;
System.out.println("Hey-your input is:"+n)

O(?)

int n = 1000;
System.out.println("Hey-your input is:"+n);
System.out.println("Hmm.. I'm doing more stuff with:"+n);
System.out.println("And more:"+n);

O(N)

for(int i=1;i<=n;i++){
   System.out.println("Hey - I'm busy looking at:"+i);
}

O(N^2)

for(int i=1;i<=n;i++){
   for(int j=1;j<=n;j++){
     System.out.println("Hey - I'm busy looking at:"+i+"and"+j);
   }
}

O(log(n))

for(int i=1;i<n;i=i*2){
   System.out.println("Hey - I'm busy looking at:"+i);
}

O(k^n)

int fib(int n){
  if(n<2) return n;
  return fib(n-1)+fib(n-2);
}

方法一：从1到n的循环累加

y = 0;
for i = 1 to n:
y += i;

时间复杂度O(n)

方法二:求和公式sum=n(n+1)/2

y = n*(n+1)/2;

时间复杂度O(1)：这段语句永远只执行一次

递归条件下分析时间复杂度

Fib:0,1,1,2,3,5,8,13,21,34, ...
F(n) = F(n-1) + F(n-2);

int fib(int n){
   int(n<2) return n;
   return fib(n-1) + fib(n-2);
}
时间复杂度O(2^n)

Master Theorem主定理

解决所有递归函数计怎么计算时间复杂度

Algorithm	Recurrence relationship	Run time
Binary search	T(n)=T(n/2) + O(1)	O(log^n)
Binary tree traversal	T(n) = 2T(n/2) +O(1)	O(n)
Optimal sorted matrix search 二维排序矩阵二分查找	T(n) = 2T(n/2) +O(log^n)	O(n)
Merge sort 归并排序	T(n) = 2T(n/2)+O(n)	O(nlog^n)

所有排序最优办法是nlog^n。

二叉树的前序，中序，后序遍历时间复杂度为O(n)。每个节点访问一次且仅访问一次，时间复杂度线性于二叉树的节点总数n。

图的遍历:时间复杂度是多少？O(n),每个节点访问一次且仅访问一次，节点总数为n。

搜索算法:DFS、BFS时间复杂度是多少？O(n)，所有节点只访问一次，节点总数为n。

二分查找:时间复杂度是多少？log^n。

空间复杂度

1.数组的长度
2.递归的深度(特殊说明)