创作不易，来了的客官点点关注，收藏，订阅一键三连?😜?

?目录

算法（algorithm）

时间复杂度

常见的基本时间复杂度

总结

? 思考：如何简单快速判断算法复杂度？

空间复杂度

空间复杂度表示方法

递归

递归的两个特点

汉诺塔问题

汉诺塔问题的递归算法代码

---

算法（algorithm）

算法是一组完成任务的指令，任何代码片段偶可以视为算法。

算法的速度

并非指的是时间，而是操作数的增速；随着输入的增加，其运行时间将以什么样的速度增加。

用大O表示，大O是什么呢？

时间复杂度

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

常见的基本时间复杂度

print("hello")???????? ????????????????????????????????????????????

时间复杂度：O(1)

for i in range(n)

???? print("hello")???????????????????????????????????????????????

时间复杂度：O(n)

for i in range(n)

??? for j in range(n)????

???????????? print("hello")????????????????????????????????????????

时间复杂度：O(n2)

for i in range(n)

???? for j in range(n)

????????? for k in range(n)

???????????????? print("hello")??????????????????????????????????????

时间复杂度：O(n3)

print("hello")

print("hello2")

print("hello3")????????????????????????????????????????????????

时间复杂度：是不是O(3)?不是---->O(1),一个量级一个统一表示。类似于我们几个小时的时候忽略了几小时的几分钟

for i in range(n)

??? print("hello")

??? for j in range(n)????

???????????? print("hello")???????????????????????????????????????

时间复杂度：是不是O(n2+n)？不是，O((n2)

while n>1

??? print(n)

??? n = n//2

n=64时，输出6次，log264=6

时间复杂度：O(logn)--->循环迭代出现规模减半的时候出现的时间复杂度

总结

1.一般来说，时间复杂度高的算法比复杂度低的算法慢

常见时间复杂度排序（效率高到低）

O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)

2.大O::指出了算法的运行时间，O(n)中n表示次数；指出了最糟情况下的运行时间。

O(n)，线性时间，线性查找。

O(log n), 对数时间，二分查找。

O(n*log n)，快速排序。

O(n^2)，选择排序。

O(n!)，旅行商问题解决方案。

?思考：如何简单快速判断算法复杂度？

①确定问题规模n

②是否循环减半？--->logn

③K层关于n的循环 -->nk

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

空间复杂度

空间复杂度：用来评估算法内存占用大小的式子

空间复杂度表示方法

空间复杂度的表示方法与时间复杂度完全一样

算法使用了几个变量：O(1)

算法使用了长度为n的一维列表：O(n)

算法使用了m行n列的二位列表：O(mn)

递归

递归的两个特点

调用自身

结束条件

以下函数哪些是递归？

func1()? --> 不是，没有结束条件

func2()? -->? 不是，伪结束条件

func3()? -->?? 属于递归，func3(3) 输出：3，2，1

func4()? -->?? 属于递归，func4(3) 输出：1，2，3

汉诺塔问题

如何移动？

n=2时：

n个盘子时：

此时只有第二步移动一步，第一步和第三步移动了n-1个盘子，它是比原问题规模（n）小了1的子问题，可以理解为递归。

汉诺塔问题的递归算法代码

def hanoi(n,a,b,c):

??? if n > 0:

??????? hanoi(n-1,a,c,b)? # n-1个盘子从a经过c移动到b

??????? print(f"第{n}个盘子 moving? from {a} to {c}") # 第n个盘子从a移动到c

??????? hanoi(n-1,b,a,c)? # 最后将n-1个盘子

?

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

# 输出结果

# 第1个盘子 moving? from A to C

# 第2个盘子 moving? from A to B

# 第1个盘子 moving? from C to B

# 第3个盘子 moving? from A to C

# 第1个盘子 moving? from B to A

# 第2个盘子 moving? from B to C

# 第1个盘子 moving? from A to C

由此：

1个盘子 --> 1步

2个盘子 --> 3步

3个盘子 --> 7步

…….

n个盘子 --> h(n)==h(n-1)+1+h(n-1)=2h(n-1)+1