大佬教程收集整理的这篇文章主要介绍了python每日算法——算法的起步与递归算法(汉诺塔问题),大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。
创作不易c;来了的客官点点关注c;收藏c;订阅一键三连❤ὡc;
目录
算法(algorithm)
时间复杂度
常见的基本时间复杂度
总结
思考:如何简单快速判断算法复杂度?
空间复杂度
空间复杂度表示方法
递归
递归的两个特点
汉诺塔问题
汉诺塔问题的递归算法代码
算法是一组完成任务的指令c;任何代码片段偶可以视为算法。
算法的速度
并非指的是时间c;而是操作数的增速;随着输入的增加c;其运行时间将以什么样的速度增加。
用大O表示c;大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)
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")
while n>1
print(n)
n = n//2
时间复杂度:O(logn)--->循环迭代出现规模减半的时候出现的时间复杂度
1.一般来说c;时间复杂度高的算法比复杂度低的算法慢
常见时间复杂度排序(效率高到低)
O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)
2.大O::指出了算法的运行时间c;O(n)中n表示次数;指出了最糟情况下的运行时间。
O(log n), 对数时间c;二分查找。
O(n*log n)c;快速排序。
O(n^2)c;选择排序。
O(n!)c;旅行商问题解决方案。
思考:如何简单快速判断算法复杂度?①确定问题规模n
②是否循环减半?--->logn
③K层关于n的循环 -->nk
④对于复杂情况:根据算法执行过程判断
空间复杂度:用来评估算法内存占用大小的式子
空间复杂度的表示方法与时间复杂度完全一样
算法使用了几个变量:O(1)
算法使用了长度为n的一维列表:O(n)
算法使用了m行n列的二位列表:O(mn)
调用自身
结束条件
以下函数哪些是递归?
func1() --> 不是c;没有结束条件
func2() --> 不是c;伪结束条件
func3() --> 属于递归c;func3(3) 输出:3c;2c;1
func4() --> 属于递归c;func4(3) 输出:1c;2c;3
如何移动?
n=2时:
n个盘子时:
此时只有第二步移动一步c;第一步和第三步移动了n-1个盘子c;它是比原问题规模(n)小了1的子问题c;可以理解为递归。
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
以上是大佬教程为你收集整理的python每日算法——算法的起步与递归算法(汉诺塔问题)全部内容,希望文章能够帮你解决python每日算法——算法的起步与递归算法(汉诺塔问题)所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。