如何判断程序的复杂程度：时间和空间复杂度
1. 时间复杂度：
使⽤⼤O表⽰法来表⽰程序的时间复杂度
常见的7种时间复杂度（复杂度由低到⾼排序）
O(1)：常数时间复杂度
O(log(n): 对数时间复杂度
O(n): 线性时间复杂度
O(n^2)：平⽅时间复杂度
O(n^3):⽴⽅时间复杂度
O(k^n)：指数时间复杂度，k表⽰常数
O(n!)：阶乘时间复杂度
ps：
这⾥我们并不考虑前边的系数；O(1) 并不表⽰复杂度为1，也可以是2、3等常数；O(n)表⽰程序运⾏了n次或者2n、3n次；以此类推其他时间复杂度
时间复杂度的判断，以⼀段代码的最⾼复杂度为准；
如何判断⼀段代码的时间复杂度
简⽽⾔之就是看内部某段代码的执⾏次数
O(1)：常数复杂度
int n = 1;
System.out.println(n);
1
2
int n = 1;
System.out.println(n);
System.out.println(n+1)
System.out.println(n+2)
1
2
3
4
O(n)：线性时间复杂度
for (int j = 0; j < n; j++) {
System.out.println(j);
}
1
2
3
for (int i = 0; i < n; i++) {
System.out.println(i);
}
for (int j = 0; j < n; j++) {
System.out.println(j);
}
1
2
3
4
5
6
O(n^2)：平⽅时间复杂度
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.println(i + j);
3
4
5
O(n^3)：⽴⽅时间复杂度
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
System.out.println(i + j);
}
}
}
1
2
3
4
5
6
7
O(log(n))：对数时间复杂度
这⾥演⽰的是以2为底n的对数
for (int i = 0; i < n; i = i * 2) {
System.out.println(i);
}
1
2
3
O(2^n)：指数时间复杂度
/**
* 递归求斐波那契数列的第n项；可以通过画运⾏树的⽅式获得时间复杂度*/
int fib(int n) {
if (n < 2) return n;
return fib(n - 1) + fib(n - 2);
}
1
2
3
4
5
6
7
O(n!)：阶乘时间复杂度
todo
⼩练习1：求和计算1~n的和
O(n)
int y = 2;
for (int i = 0; i < n; i++) {
y+=i;
}
1
2
3
4
O(1)
使⽤了求和公式：sum = n(n+1)/2
int y = 2;
for (int i = 0; i < n; i++) {
y+=i;
4
⼩练习2：求斐波那契数列
O(2^n):
int fib(int n) {
if (n < 2) return n;
return fib(n - 1) + fib(n - 2);
}
1
2
3
4
O(n)：该⽅法⽐递归要快得多
int fib2(int n) {
if (n == 1 || n == 2) {
return 1;
}
int a = 1, b = 1, result = 0;
for (int i = 3; i <= n; i++) {
result = a + b;
a = b;
b = result;
}
return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
主定理
主定理（英语：master theorem）提供了⽤渐近符号（⼤O符号）表⽰许多由分治法得到的递推关系式的⽅法
常⽤算法中的应⽤
算法递回关系式运算时间
⼆分搜寻算法
⼆叉树遍历
最佳排序矩阵搜索(已排好序的⼆维矩阵)
合并排序
所有排序的最优算法都是O(nlog(n))
2. 空间复杂度
如何判断⼀段代码的空间复杂度
主要通过两部分进⾏判断：
数组的长度
如果代码中应⽤了数组，那么数组的长度，基本上就是空间复杂度；
e：⼀维数组的空间复杂度是O(n);⼆维数组的空间复杂度是O(n^2)
递归的深度
如果代码中有递归，那么递归的深度，就是代码的空间复杂度的最⼤值
ps：如果代码中既有数组，⼜有递归，那么两者的最⼤值就是代码的空间复杂度
leecode有个爬楼梯的复杂度分析情况；可以进⾏练习
3. 数组和链表的时间复杂度分析
数组
随机增加：O(n)
随机查询：O(1)
随机删除：O(n)
链表
数组和链表
随机增加：O(1)
随机查询：O(n)
随机删除：O(1)
跳表
跳跃表（skiplist）是⼀种随机化的数据，由 William Pugh 在论⽂《Skip lists: a probabilistic alternative to balanced trees》中提出，跳跃表以有序的⽅式在层次化的链表中保存元素，效率和平衡树媲美 —— 查、删除、添加等操作都可以在对数期望时间下完成，并且⽐起平衡树来说，跳跃表的实现要简单直
观得多。
简单来说，跳跃表是有序链表的⼀种扩展，在有序列表的基础上进⾏了升维处理

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。