Py008-01-01算法基础

算法入门

  • 什么是算法 Algorithm

一个计算过程，解决问题的方法

Niklaus Wirth:程序=数据结构+算法

时间复杂度

生活中一些事情，估计时间

1
2
3
4
5
6
7
8
9
10
11
眨眼     一瞬间

口算 29+68   几秒钟

烧一壶水    几分钟

睡一觉    几小时

完成一个项目   几天/几周/几个月

飞船从地球到太阳系   几年

如下代码那个运行最短？

用来评估算法运行效率的一个式子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#时间复杂度   O(1)
print('hi')   


#时间复杂度   O(n)
for i in range(n):
    print('hi')


#时间复杂度   O(n*n)
for i in range(n):
    for j in range(n):
        print('hi')

#时间复杂度   O(n*n*n)
for i in range(n):
    for j in range(n):
        for k in range(n):
            print('hi')

继续看

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#时间复杂度   不是O(3)  而是 O(1)
print('hi')
print('hi')
print('hi')
# why?
# 比如生活角度的烧水  没人回答你   3个3分钟 而是回答  几分钟  

#时间复杂度   不是O(n*n+n)  而是O(n*n)
for i in range(n):
    print('hi')
    for j in range(n):
        print('hi')

# why?
# 比如生活角度的睡觉  没人回答你   7个小时零20分 而是回答  几小时

再看

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
while n > 1:
    print(n)
    n = n // 2

n=64输出
64
32
16
8
4
2

每次少一半 （对数形式）
2*2*2*2*2*2 = 64
log64 = 6
时间复杂度为 O(log n)

时间复杂度小结

  • 用来估计算法运行时间的式子
  • 时间复杂度高的算法比复杂度低的算法慢

  • 常见时间复杂度(按效率排序)
    O(1)<O(log n)<O(n)<O(n log n)<O(nn)<O(nn log n)<O(nnn)

  • 复杂的时间复杂度
    O(n!) O(2的n次方) O(n的n次方) …

如何简单快速判断算法复杂度

常见情况

  • 确定问题规模的n
  • 循环减半过程 –> log n
  • k层关于n的循环 –> n的k次方

复杂情况：根据算法执行过程判断

空间复杂度

  • 评估算法内存占用大小的式子
  • 空间复杂度的表达方式和时间复杂度完全一样
    算法使用了几个变量O(1)
    算法使用了长度为n的一维列表 O(n)
    算法使用了长度为m行n列的一维列表 O(m*n)
  • 空间换时间

由于现在内存和硬件水平的提升所以空间已经不是那么重要了