时间复杂度

常用的时间复杂度

O(1): Constant Complexity 常数复杂度

int n = 1000;
System.out.println(n);
System.out.println("Hey - I'm busy looking at: " + n);

O(log n): Logarithmic Complexity 对数复杂度

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

O(n): Linear Complexity 线性时间复杂度

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

O(n^2): N square Complexity 平⽅

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(n^3): N square Complexity ⽴⽅

O(2^n): Exponential Growth 指数

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

O(n!): Factorial 阶乘

递归是如何计算时间复杂度的？

画出一个树状图，如 fib 数列

可以看到每一层都是 2 的指数，所以这是一个 O(2^n)

时间复杂度曲线

固定公式

二分查找：O(log n)

二叉树搜索：O(n)

二维矩阵查找： O(n)

归并排序：O(n log n)

某些常见题目就用到

• ⼆叉树遍历 - 前序、中序、后序：O(N)
• 图的遍历：O(N)
• 搜索算法：DFS、BFS - O(N)
• ⼆分查找：O(logN)