马上注册，结交更多好友，享用更多功能^_^
您需要 登录 才可以下载或查看，没有账号？立即注册
x
第002讲：你怎么知道你的程序跑得比别人快
知识点回顾：
0. 本节视频
1. 破解猜数字游戏
在《零基础入门学习Python》的课程中，小甲鱼是以一个猜数字的游戏来引入，开启了我们的Python学习之旅。那么这一节课，咱们同样是通过这个游戏，来探讨算法的奥妙：
""" 用Python设计第一个游戏 """
import random
# 玩家总共有十次机会
counts = 10
# 获取一个1~10的随机数
answer = random.randint(1, 10)
while counts > 0:
temp = input("不妨猜一下小甲鱼现在心里想的是哪个数字：")
guess = int(temp)
if guess == answer:
# 当玩家猜中结果的时候
print("你是小甲鱼心里的蛔虫嘛？！")
print("哼，猜中了也没奖励！")
break
else:
# 当玩家没有猜中结果的时候
if guess < answer:
print("小啦~")
else:
print("大啦~")
counts = counts - 1
print("游戏结束，不玩啦^_^")
根据游戏的规则，以及生活经验带给我们的智慧，自然而然就会想到，从中间这个数字下手。
比如这里的范围是 1~10，我们就输入 5，如果提示 “小啦”，那我们再从 6~10 之间找一个中间数 8，如果又提示 “小啦”，那么现在我们就剩下 50% 的概率了，要么结果是 9，要么就是 10。
只要采用这种朴素的方法，每猜一次数字，我们都可以排除掉一半的错误选项。
所谓出道即巅峰，这其实是一种效率非常高的查找算法，它是有一个名字的，叫二分查找算法（Binary search algorithm），也称为折半搜索算法。
如果我们将问题的规模扩大 10 倍（猜 1~100 的随机数），那么最多的尝试次数也只是从 4 次提升到 7 次。
如果我们将问题的规模继续扩大 10 倍（猜 1~1000 的随机数），那么最多的尝试次数也只是 10 次。
由于二分查找算法每次我们都会砍掉一半的候选项，也就是 100 变成 50，50 变成 25，以此类推……
第一次减半，第二次变成四分之一，第三次变成八分之一，因此我们最多需要尝试的次数就是 log2n。
2. 时间复杂度
这一节课的主题是 —— 你怎么知道你的程序跑得比别人快？
也就是如何去衡量一个算法的快慢呢？
在数据结构和算法这个领域，大家是使用大O表示法（Big O notation）来描述一个算法的快慢。
下面给大家介绍一些常见的时间复杂度：
O(1) < O(logn) < O(n) < O(nlogn) < O(n2)
O(n2) < O(n3) < O(2n) < O(n!) < O(nn)
3. 旅行商问题
解决一个问题，我们都要尽可能地选择时间复杂度低的算法。
不过，有时候也会遇到极端的问题，比如旅行商问题。
旅行商问题（Traveling Salesman Problem，TSP）是一种经典的组合优化问题。
在这个问题中，假设有一个旅行商要拜访一系列的城市，并返回起始城市。
每个城市之间的距离是已知的，并且每个城市只能被访问一次。旅行商的目标是找到一条路径，使得他能够经过所有的城市，总路程最短。
具体地说，对于 N 个城市的 TSP 问题，穷举搜索的时间复杂度为 O(N!)，即阶乘级别。
这是因为在每个城市，旅行商都有 N-1 个选择，因此总共有 N! 种可能的路径。
4. 思维导图
| 
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 2023-8-7 01:32:23
置顶卡
千斤顶
显身卡
发表于 2023-8-9 10:32:04