程序 = 数据结构+算法
一个程序，有多种解决实际问题的解法，就涉及到算法；听说多训练算法思维，测试过程基本也不会漏测，赶紧多训练下；
本篇主要理解下算法解题中涉及到的几种概念，时间复杂度+空间复杂度
1、时间复杂度：用来评估算法运行效率的式子
image.png
小结：
1、算法要考虑时间复杂度。时间复杂度是用来估计算法运行时间的一个式子（单位）。
2、一般来说，时间复杂度高的算法比复杂度低的算法慢。
3、常见的时间复杂度（按效率排序）：
O(1)>O(logn)>O(n)>O(nlogn)>O(n2)>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')
网友评论