第002讲：你怎么知道你的程序跑得比别人快
第002讲：你怎么知道你的程序跑得比别人快知识点回顾：
0. 本节视频
https://www.bilibili.com/video/BV12m4y1e7iY/?p=2
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. 思维导图
沙发 努力学习 本周签到 ilovefishc 你怎么知道你的程序跑得比别人快 llovefishc 刚开始学习《零基础入门学习Python》，嗯一点一点来吧，加油！ llovefishc 努力向大佬靠拢! 感谢分享，辛苦了！ 打卡学习，一天也不掉队 小甲鱼牛牛牛 努力学习 打卡 学习，进步 努力学习 程序跑得快 一起努力！！！ good
你很棒棒哦~
页:
[1]
2