03.python算法基础知识理解

程序 = 数据结构+算法
一个程序，有多种解决实际问题的解法，就涉及到算法；听说多训练算法思维，测试过程基本也不会漏测，赶紧多训练下；
本篇主要理解下算法解题中涉及到的几种概念，时间复杂度+空间复杂度

1、时间复杂度：用来评估算法运行效率的式子

image.png

小结：

1、算法要考虑时间复杂度。时间复杂度是用来估计算法运行时间的一个式子（单位）。
2、一般来说，时间复杂度高的算法比复杂度低的算法慢。
3、常见的时间复杂度（按效率排序）：
O(1)>O(logn)>O(n)>O(nlogn)>O(n^2)>O(n2logn)>O(n^3)
这个时间复杂度中log都是以2为底的对数。
3、不常见的时间复杂度：
O(n!), O(2^n), O(n^n)
4、怎样判断时间复杂度：确定问题规模n，循环减半的过程是 O(logn)，几次循环就是n的几次方的复杂度

2、空间复杂度

时间复杂度比空间复杂度重要，所以有很多分布式算法

3、递归

image.png

递归实例：汉诺塔问题

image.png

def hanoi(n,a,b,c):
    if n >0:
        hanoi(n-1,a,c,b)
        print("moving from %s to %s"%(a,c))
        hanoi(n-1,b,a,c)

hanoi(3,'A','B','C')