文章目录
- 时间复杂度的概念
- 时间复杂度：常[1]、对[logn]、幂[n^2]、 指[2^n]、阶[n!]
- 例题
- ❗易错提醒
- 空间复杂度
- 🍔算法原地工作：算法所需的内存空间为常量
- 例题
时间复杂度的概念
例1：假设 n = 3000 n=3000 n=3000
i=2998,print("I love You %d\n",i)
i=2999,print("I love You %d\n",i)
i=3000,print("I love You %d\n",i)
当i=3001,经过判断，i<=n不成立
所以，while循环执行3001次(步骤2)，while循环里面的++、print执行了3000次，其它1、5执行了1次
T(3000)=1+3001+2x3000+1，所以T(n)=3n+3,n=3000
🔥结论：计算时间复杂度只需要考虑阶数高的部分
-
加法规则
多项相加，只保留最高阶的项，并且系数变为1
-
乘法规则
时间复杂度：常[1]、对[logn]、幂[n^2]、 指[2^n]、阶[n!]
🌈时间复杂度的大小关系：
O
(
1
)
<
O
(
log
2
n
)
<
O
(
n
)
<
O
(
n
log
2
n
)
<
0
(
n
2
)
<
O
(
n
3
)
<
0
(
2
n
)
<
O
(
n
!
)
<
O
(
n
n
)
O(1)<O\left(\log _{2} n\right)<O(n)<O\left(n \log _{2} n\right)<0\left(n^{2}\right)<O\left(n^{3}\right)<0\left(2^{n}\right)<O(n !)<O\left(n^{n}\right)
O(1)<O(log2n)<O(n)<O(nlog2n)<0(n2)<O(n3)<0(2n)<O(n!)<O(nn)
例题
❗易错提醒
-
程序不一定满足有穷性，如死循环、操作系统等；而算法必须有穷
-
算法满足5个基本特性（这是算法的要求而不是定义）
-
算法的时间复杂度为 O ( n 2 ) O(n^2) O(n2)，在这里问题规模是 n n n，时间复杂度是 O ( n 2 ) O(n^2) O(n2)
-
在相同的规模下， O ( n ) < O ( n 2 ) O(n)<O(n^2) O(n)<O(n2)
✅正确！时间复杂度制定了n无穷大，故不能带入特殊值n0考虑
空间复杂度
🍔算法原地工作：算法所需的内存空间为常量
1个int变量占4Byte,32bit
例题
所以，空间复杂度等于递归调用的深度
