目录
数据结构与算法(Python版)
# 1. 入门1.1 算法概念
概念： 算法就是一个计算过程，解决问题的方法
程序 = 数据结构 + 算法
1.2 时间复杂度
-
时间复杂度是用来估计算法运行时间的一个式子（单位）
-
一般来说，时间复杂度高的算法比复杂度低的算法慢
-
常见的时间复杂度（按照效率排序）
-
O(1) < O(log n) < O(n) < O(n log n) < O(n2) < O(n2 log n) < O(n3)
-
-
复杂问题的时间复杂度
-
O(n!) O(2n) O(nn) .......
-
-
快速判断算法复杂度（适用于大多情况）
-
确定问题规模 n
-
循环减半过程 ----- log n
-
k层关于n的循环------- nk
-
-
复杂情况：根据算法执行过程判断
1.3 空间复杂度
-
空间复杂度就是评估内存占用大小的式子
-
空间复杂度的表示方式与时间复杂度完全一致
-
算法使用了几个变量: O( 1 )
-
算法使用了长度为 n 的一维列表：O( n )
-
算法使用了m行n列的二维列表： O( mn )
-
-
空间换时间
1.4 递归
-
递归的两个特点
-
调用自身
-
结束条件
-
1.5 汉诺塔问题
def hanoi(n, a, b, c):
if n>0:
hanoi(n-1, b, c, a)
print("{} 移动到 {}".format(a, c))
hanoi(n-1, b, a, c)
pass
pass
hanoi(64,"A", "B", "C")