❤️算法离我们并不远❤️为什么你排位总是输,原因在这

2024-01-06 18:50

本文主要是介绍❤️算法离我们并不远❤️为什么你排位总是输,原因在这,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

前言

文章摘抄至《算法之美》,附带了Python模拟。

不久前,我去观看草地网球锦标赛,一位十分沮丧的运动员引起了我对球赛目前采用的名次确定方法的注意。这位运动员在比赛中早早落败,因此彻底失去了获得奖牌的机会。令他感到屈辱的是,获得第二名的是他知道的一名远不如自己的运动员。

在这里插入图片描述


普通观众可能会把这种“哀叹”归咎于失败的痛苦,但道奇森并不是一个同情心泛滥的人,他是牛津大学数学系讲师,因此,在听到运动员的抱怨之后,他决定对体育赛事展开深入调查。道奇森不仅仅是一个数学家(其实他几乎不记得自己是从事数学研究的)。现在,反而是他的笔名——刘易斯·卡罗尔更加广为人知。他以这个笔名写出了《爱丽丝漫游奇境记》以及大量其他深受欢迎的文学作品。他还将他的数学知识与文学天赋相结合,完成了一篇知名度略低的文章——《草地网球锦标赛:正确的名次确定方法以及现行方法辨误》。

道奇森针对的是单一淘汰赛。在这种赛制下,运动员两两对决,只要输掉一场比赛,就会被淘汰出局。道奇森的理由非常有说服力,他认为,货真价实的第二名有可能是被第一名淘汰的任何人,而不一定是最后才被淘汰的那名运动员。

在这里插入图片描述


直白地说,银牌是一种假象。“作为一个数学事实,”他继续写道,“实力排第二位的运动员获得应得名次的机会只有16/31。而最优秀的4名运动员获得与实力相称名次的机会非常小,发生的概率为1/12!”

这里可以借助Python演示一下(语言不重要,可以改成自己熟悉的。)

import copy
import randomclass Participants():def __init__(self,*_participants):self.name = _participants[0]  # 1号球员self.performance =_participants[1]   # 自身成绩self.racePlaces = _participants[2]  # 比赛名次# 实例100个选手,并且假设从5号以后的选手,实例都不如前4个
arrPart=[]
arrPart.append(Participants('No.1',100,0,0))
arrPart.append(Participants('No.2',99,0,0))
arrPart.append(Participants('No.3',98,0,0))
arrPart.append(Participants('No.4',97,0,0))
for i in range(5,101):arrPart.append(Participants(f'No.{i}', random.randint(0,96), 0, 0))# 单场比赛(传入2个人员,和名次)返回,胜利者、失败者
def race(one,two,topNum):unitRace=[]if(one.performance > two.performance):print(f"{one.name}{two.name}比赛,{one.name}胜利")one.racePlaces=topNumtwo.racePlaces=topNum-1unitRace.append(one)unitRace.append(two)return one,twoelse:print(f"{one.name}{two.name}比赛,{two.name}胜利")two.racePlaces=topNum-1unitRace.append(two)one.racePlaces=topNumunitRace.append(one)return two,one# 排位开始
def knockout(all):arrVictory=[]   #保存胜利者# 选出前4名后结束if(len(all)<=3):print("++++++++++++++++++=================")print(all[1].name)return all# 依次进行两两比赛,同批次淘汰赛只参加一次while( len(all) > 1 ):topNum=len(all)r=random.randint(0,len(all)-1)one=all[r]# 参赛后,从当前候选名单删除all.remove(one)r=random.randint(0,len(all)-1)two=all[r]all.remove(two)victory,fail=race(one,two,topNum)print(victory.name)arrVictory.append(victory) # 添加胜利者# 没有进行匹配的直接晋级if( len(all) == 1):arrVictory.append(all[0])print("***********************--------------------------")# 下一轮淘汰赛return knockout(arrVictory)# 统计1000次模拟种有几次实力3号选手能进前三
isNO2count=0
for i in range(1000):arrPart1=copy.copy(arrPart)victorys=knockout(arrPart1)for v in victorys:if v.name=='No.3':print("名次:%d"%(v.racePlaces))isNO2count += 1break
print(isNO2count)

== 看输出结果,我们很容易发现,结果在22-28%之间徘徊。 ==
而只有把if v.name==‘No.3’:的No.3改成No.1才会是100%。


尽管道奇森的文章犀利有力,却没有对草地网球产生任何影响。他提出应该采取三败淘汰制(根据这种赛制,击败过你的运动员如果落败,也有可能导致你随之出局),但是这个提议根本没有人理会。不过,虽然道奇森的解决方案实施起来有很大的难度,但是他在这个问题上的看法仍然是有道理的。(可惜的是,至今为止,在单淘汰赛中,仍然会颁发银牌。)不过,道奇森的逻辑还给我们带来了一个更加深刻的认识。我们人类不仅会对数据、财产进行排序,还会把我们自己变成排序对象。

世界杯、奥运会、美国全国大学体育协会(NCAA)、美国全国橄榄球联盟(NFL)、美国全国曲棍球联合会(NHL)、美国职业篮球联赛(NBA)和美国职业棒球大联盟(MLB),所有这些赛事都毫无疑问地使用了排序程序,利用赛季、排位赛和季后赛等算法排出先后关系。体育运动中的循环赛制就利用了算法。如果一共有n支运动队,那么每支运动队最终都要和其余n-1支队伍比赛。这种赛制虽然可以说是最全面的,但也最费时费力。

让每一支运动队都与其他所有队伍比赛,就像在晚宴上让客人两两拥抱一样,最终会需要可怕的O(n2)次角逐。排位赛(在羽毛球、英式壁球和美式壁球等体育项目中比较常见)对运动员进行线性排序,每个球员都可以直接向排在前面一位的球员发起挑战,如果获胜,则交换排位。排位赛就相当于运动场上的冒泡排序,因此也是平方排序,需要O(n2)场比赛才能得到稳定的排名。

到这里就要提到算法的两个基础概念:

1.时间复杂度

「 大O符号表示法 」,即 T(n) = O(f(n))
在 大O符号表示法中,时间复杂度的公式是: T(n) = O( f(n) ),其中f(n) 表示每行代码执行次数之和,而 O 表示正比例关系,这个公式的全称是:算法的渐进时间复杂度。

** 在刚刚的演示代码中,race函数的执行次数就是一个时间复杂度的统计,所以,该程序的时间复杂度为O(n log n) **

3.空间复杂度

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的一个量度,同样反映的是一个趋势,我们用 S(n) 来定义。

** 在刚刚的演示代码中,一个人/同一时间,只有一个场地比赛,所以,它的空间复杂度为S(1) **

原文补充:

不过,最流行的赛制可能还是分组淘汰——著名的“疯狂三月”NCAA篮球赛就是其中一例。“疯狂三月”锦标赛的赛程包含“64强赛”“32强赛”到“甜蜜16强”“8强赛”“最后4强”和总决赛。每一轮都会导致比赛人数减半。与我们熟悉的对数排序很像吧?这种赛制其实就是合并排序,先让球队无序配对,然后进行一轮又一轮的比较。
我们知道合并排序需要线性对数时间[即O(n log n)],因此,如果一共有64支队伍,可以预计比赛只需要进行6轮(一共192场),而采用排位赛或者循环赛,则需要多达63轮(2016场)比赛。这是一个巨大的改进,说明对数设计发挥了效用。

“疯狂三月”有6轮比赛,似乎没有问题,但是怎么是192场比赛呢?
美国大学体育协会锦标赛不是只有63场比赛吗?


“疯狂三月”其实不完全是一种合并排序法,因为它并没有产生所有64支队伍的完整排序。要对所有球队进行排名,我们需要增加一组比赛才能确定第二名,确定第三名时又需要增加一组比赛,以此类推,比赛的总场次就会是一个线性对数函数。但是“疯狂三月”没有采取这种赛制。相反,就像道奇森抱怨的草地网球锦标赛一样,它采用的是一种单一淘汰制,被淘汰的球队是不排序的。这种赛制的优势在于它的线性时间。由于每场比赛正好淘汰一支队伍,因此,要让一支队伍留到最后,一共需要n-1场比赛。这是一个线性数字。不足之处是,这种赛制只能决出第一名,无法给出名次表。

最后

很多优秀的算法,很容易在生活中找到案例,同时也可以把算法技巧用在生活和工作上。
书名为《算法之美–指导工作与生活的算法》
在这里插入图片描述

同时推荐一本《数据结构与算法__Python语言描述_裘宗燕编著_北京:机械工业出版社》

在这里插入图片描述

我很少大范围的推荐资料,知道什么是有用的,可以帮助自己少走很多弯路,需要的小伙伴,网盘自取:
链接: https://pan.baidu.com/s/1W8p4xXO7XaZiUxXgS9VjIQ 提取码: qrej 复制这段内容后打开百度网盘手机App,操作更方便哦

在这里插入图片描述

最后,感谢大家三连关注,支持一波。
在这里插入图片描述

这篇关于❤️算法离我们并不远❤️为什么你排位总是输,原因在这的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/577275

相关文章

流媒体平台/视频监控/安防视频汇聚EasyCVR播放暂停后视频画面黑屏是什么原因?

视频智能分析/视频监控/安防监控综合管理系统EasyCVR视频汇聚融合平台,是TSINGSEE青犀视频垂直深耕音视频流媒体技术、AI智能技术领域的杰出成果。该平台以其强大的视频处理、汇聚与融合能力,在构建全栈视频监控系统中展现出了独特的优势。视频监控管理系统EasyCVR平台内置了强大的视频解码、转码、压缩等技术,能够处理多种视频流格式,并以多种格式(RTMP、RTSP、HTTP-FLV、WebS

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

【测试】输入正确用户名和密码,点击登录没有响应的可能性原因

目录 一、前端问题 1. 界面交互问题 2. 输入数据校验问题 二、网络问题 1. 网络连接中断 2. 代理设置问题 三、后端问题 1. 服务器故障 2. 数据库问题 3. 权限问题: 四、其他问题 1. 缓存问题 2. 第三方服务问题 3. 配置问题 一、前端问题 1. 界面交互问题 登录按钮的点击事件未正确绑定,导致点击后无法触发登录操作。 页面可能存在

秋招最新大模型算法面试,熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候,不知道面试完会不会复盘、总结,做笔记的习惯,这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助,都附有完整答案,熬夜也要看完,祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN,还有完整版的大模型 AI 学习资料,朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费

dp算法练习题【8】

不同二叉搜索树 96. 不同的二叉搜索树 给你一个整数 n ,求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种?返回满足题意的二叉搜索树的种数。 示例 1: 输入:n = 3输出:5 示例 2: 输入:n = 1输出:1 class Solution {public int numTrees(int n) {int[] dp = new int