python|算法的时间复杂度算法|数据结构|Python|时间复杂

算法的时间复杂度

什么是时间复杂度？
- 易错点 1：注意单位而不是次数
- 易错点 2：注意大约而不是准确
- 重难点：时间复杂度里的对数
小结

什么是时间复杂度？用来评估算法运行效率的一个式子

print('hello world')

此处时间复杂度可以表示为： O ( 1 ) O(1) O(1)
O O O表示大约的意思， 1 1 1在这里表示的是单位的意思，即大约运行以 1 1 1为单位的时间。

for i in range(n): print('hello world')

此处时间复杂度可以表示为： O ( n ) O(n) O(n)
因为此处循环 n n n次，即大约运行以 n n n为单位的时间。

for i in range(n): for j in range(n): print('hello world')

此处时间复杂度可以表示为： O ( n 2 ) O(n^2) O(n2)
因为此处循环 n ? n n*n n?n次，即大约运行以 n 2 n^2 n2为单位的时间。
易错点 1：注意单位而不是次数

print('hello world') print('hello world') print('hello world')

此处的时间复杂度各位认为可以表示为什么呢？ O ( 3 ) O(3) O(3)?
此处的时间复杂度仍表示为： O ( 1 ) O(1) O(1)

【python|算法的时间复杂度】 O ( ) O() O()括号里面内容表示单位的意思，而不代表次数。运行三次，三是个量词，三次代表次数而不是单位，若将其视为单位则可以理解为运行时间大约以 n 0 n^0 n0为单位。

易错点 2：注意大约而不是准确

for i in range(n): print('hello world') for j in range(n): print('hello world')

再看到此处，时间复杂度各位认为可以表示为什么呢？ O ( n 2 + n ) O(n^2+n) O(n2+n)?
此处的时间复杂度仍表示为： O ( n 2 ) O(n^2) O(n2)

O ( ) O() O()中的 O O O表示的是大约的意思，而不是准确。当 n n n非常大时， n 2 n^2 n2将远大于 n n n， n n n即可忽略不计。因此可以理解为运行时间大约以 n 2 n^2 n2为单位。

重难点：时间复杂度里的对数

while n > 1: print(n) n = n // 2

此次的时间复杂度各位认为又是多少呢？
当n = 64 n=64 n=64 时，输出：64 42 16 8 4 2
共计6 6 6 次， 2 6 = 64 2^6=64 26=64， l o g ? 64 = 6 log?64=6 log?64=6
其中n n n 为64 64 64 ，这里把6 6 6 次视为单位的话，即l o g ? n = 单位 log?n=单位 log?n=单位
所以此处的时间复杂度记为 O ( l o g ? n ) O(log?n) O(log?n)或 O ( l o g n ) O(logn) O(logn)

当算法过程中出现循环折半的时候复杂度式子中会出现l o g n logn logn

小结

时间复杂度是用来估计算法运行时间的一个式子（单位）；
**一般来说，**时间复杂度高的算法比复杂度低的算法慢；
常见的时间复杂度（按效率排序）
O ( 1 ) < O ( l o g n ) < O ( n ) < O ( n l o g n ) < O ( n 2 ) < O ( n 2 l o g n ) < O ( n 3 ) O(1)
复杂问题的时间复杂度（不常见的时间复杂度）
O ( n ! ) O(n!) O(n!)O ( 2 n ) O(2^n) O(2n)O ( n n ) O(n^n) O(nn)
快速判断算法的复杂度（适用于绝大多数简单情况，复杂情况的话就根据算法执行过程判断）
1. 确认问题规模n n n
2. 循环减半过程 —>l o g n logn logn
3. k k k 层关于 n n n的循环 —>n k n^k nk