文章摘抄至《算法之美》,附帶了Python模擬。
不久前,我去觀看草地網(wǎng)球錦標(biāo)賽,一位十分沮喪的運(yùn)動員引起了我對球賽目前采用的名次確定方法的注意。這位運(yùn)動員在比賽中早早落敗,因此徹底失去了獲得獎牌的機(jī)會。令他感到屈辱的是,獲得第二名的是他知道的一名遠(yuǎn)不如自己的運(yùn)動員。
普通觀眾可能會把這種“哀嘆”歸咎于失敗的痛苦,但道奇森并不是一個同情心泛濫的人,他是牛津大學(xué)數(shù)學(xué)系講師,因此,在聽到運(yùn)動員的抱怨之后,他決定對體育賽事展開深入調(diào)查。道奇森不僅僅是一個數(shù)學(xué)家(其實(shí)他幾乎不記得自己是從事數(shù)學(xué)研究的)?,F(xiàn)在,反而是他的筆名——劉易斯·卡羅爾更加廣為人知。他以這個筆名寫出了《愛麗絲漫游奇境記》以及大量其他深受歡迎的文學(xué)作品。他還將他的數(shù)學(xué)知識與文學(xué)天賦相結(jié)合,完成了一篇知名度略低的文章——《草地網(wǎng)球錦標(biāo)賽:正確的名次確定方法以及現(xiàn)行方法辨誤》。
道奇森針對的是單一淘汰賽。在這種賽制下,運(yùn)動員兩兩對決,只要輸?shù)粢粓霰荣?,就會被淘汰出局。道奇森的理由非常有說服力,他認(rèn)為,貨真價實(shí)的第二名有可能是被第一名淘汰的任何人,而不一定是最后才被淘汰的那名運(yùn)動員。
直白地說,銀牌是一種假象?!白鳛橐粋€數(shù)學(xué)事實(shí),”他繼續(xù)寫道,“實(shí)力排第二位的運(yùn)動員獲得應(yīng)得名次的機(jī)會只有16/31。而最優(yōu)秀的4名運(yùn)動員獲得與實(shí)力相稱名次的機(jī)會非常小,發(fā)生的概率為1/12!”
import copyimport randomclass Participants(): def __init__(self,*_participants): self.name = _participants[0] # 1號球員 self.performance =_participants[1] # 自身成績 self.racePlaces = _participants[2] # 比賽名次# 實(shí)例100個選手,并且假設(shè)從5號以后的選手,實(shí)例都不如前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=topNum two.racePlaces=topNum-1 unitRace.append(one) unitRace.append(two) return one,two else: print(f"{one.name}和{two.name}比賽,{two.name}勝利") two.racePlaces=topNum-1 unitRace.append(two) one.racePlaces=topNum unitRace.append(one) return two,one# 排位開始def knockout(all): arrVictory=[] #保存勝利者 # 選出前4名后結(jié)束 if(len(all)<=3): print("++++++++++++++++++=================") print(all[1].name) return all # 依次進(jìn)行兩兩比賽,同批次淘汰賽只參加一次 while( len(all) > 1 ): topNum=len(all) r=random.randint(0,len(all)-1) one=all[r] # 參賽后,從當(dāng)前候選名單刪除 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) # 添加勝利者 # 沒有進(jìn)行匹配的直接晉級 if( len(all) == 1): arrVictory.append(all[0]) print("***********************--------------------------") # 下一輪淘汰賽 return knockout(arrVictory)# 統(tǒng)計1000次模擬種有幾次實(shí)力3號選手能進(jìn)前三isNO2count=0for 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 += 1 breakprint(isNO2count)
== 看輸出結(jié)果,我們很容易發(fā)現(xiàn),結(jié)果在22-28%之間徘徊。 ==
而只有把if v.name==‘No.3’:的No.3改成No.1才會是100%。
盡管道奇森的文章犀利有力,卻沒有對草地網(wǎng)球產(chǎn)生任何影響。他提出應(yīng)該采取三敗淘汰制(根據(jù)這種賽制,擊敗過你的運(yùn)動員如果落敗,也有可能導(dǎo)致你隨之出局),但是這個提議根本沒有人理會。不過,雖然道奇森的解決方案實(shí)施起來有很大的難度,但是他在這個問題上的看法仍然是有道理的。(可惜的是,至今為止,在單淘汰賽中,仍然會頒發(fā)銀牌。)不過,道奇森的邏輯還給我們帶來了一個更加深刻的認(rèn)識。我們?nèi)祟惒粌H會對數(shù)據(jù)、財產(chǎn)進(jìn)行排序,還會把我們自己變成排序?qū)ο蟆?br />
世界杯、奧運(yùn)會、美國全國大學(xué)體育協(xié)會(NCAA)、美國全國橄欖球聯(lián)盟(NFL)、美國全國曲棍球聯(lián)合會(NHL)、美國職業(yè)籃球聯(lián)賽(NBA)和美國職業(yè)棒球大聯(lián)盟(MLB),所有這些賽事都毫無疑問地使用了排序程序,利用賽季、排位賽和季后賽等算法排出先后關(guān)系。體育運(yùn)動中的循環(huán)賽制就利用了算法。如果一共有n支運(yùn)動隊(duì),那么每支運(yùn)動隊(duì)最終都要和其余n-1支隊(duì)伍比賽。這種賽制雖然可以說是最全面的,但也最費(fèi)時費(fèi)力。
讓每一支運(yùn)動隊(duì)都與其他所有隊(duì)伍比賽,就像在晚宴上讓客人兩兩擁抱一樣,最終會需要可怕的O(n2)次角逐。排位賽(在羽毛球、英式壁球和美式壁球等體育項(xiàng)目中比較常見)對運(yùn)動員進(jìn)行線性排序,每個球員都可以直接向排在前面一位的球員發(fā)起挑戰(zhàn),如果獲勝,則交換排位。排位賽就相當(dāng)于運(yùn)動場上的冒泡排序,因此也是平方排序,需要O(n2)場比賽才能得到穩(wěn)定的排名。
「 大O符號表示法 」,即 T(n) = O(f(n))
在 大O符號表示法中,時間復(fù)雜度的公式是: T(n) = O( f(n) ),其中f(n) 表示每行代碼執(zhí)行次數(shù)之和,而 O 表示正比例關(guān)系,這個公式的全稱是:算法的漸進(jìn)時間復(fù)雜度。
** 在剛剛的演示代碼中,race函數(shù)的執(zhí)行次數(shù)就是一個時間復(fù)雜度的統(tǒng)計,所以,該程序的時間復(fù)雜度為O(n log n) **
空間復(fù)雜度是對一個算法在運(yùn)行過程中臨時占用存儲空間大小的一個量度,同樣反映的是一個趨勢,我們用 S(n) 來定義。
** 在剛剛的演示代碼中,一個人/同一時間,只有一個場地比賽,所以,它的空間復(fù)雜度為S(1) **
不過,最流行的賽制可能還是分組淘汰——著名的“瘋狂三月”NCAA籃球賽就是其中一例?!隘偪袢隆卞\標(biāo)賽的賽程包含“64強(qiáng)賽”“32強(qiáng)賽”到“甜蜜16強(qiáng)”“8強(qiáng)賽”“最后4強(qiáng)”和總決賽。每一輪都會導(dǎo)致比賽人數(shù)減半。與我們熟悉的對數(shù)排序很像吧?這種賽制其實(shí)就是合并排序,先讓球隊(duì)無序配對,然后進(jìn)行一輪又一輪的比較。
我們知道合并排序需要線性對數(shù)時間[即O(n log n)],因此,如果一共有64支隊(duì)伍,可以預(yù)計比賽只需要進(jìn)行6輪(一共192場),而采用排位賽或者循環(huán)賽,則需要多達(dá)63輪(2016場)比賽。這是一個巨大的改進(jìn),說明對數(shù)設(shè)計發(fā)揮了效用。
“瘋狂三月”有6輪比賽,似乎沒有問題,但是怎么是192場比賽呢?
美國大學(xué)體育協(xié)會錦標(biāo)賽不是只有63場比賽嗎?
“瘋狂三月”其實(shí)不完全是一種合并排序法,因?yàn)樗]有產(chǎn)生所有64支隊(duì)伍的完整排序。要對所有球隊(duì)進(jìn)行排名,我們需要增加一組比賽才能確定第二名,確定第三名時又需要增加一組比賽,以此類推,比賽的總場次就會是一個線性對數(shù)函數(shù)。但是“瘋狂三月”沒有采取這種賽制。相反,就像道奇森抱怨的草地網(wǎng)球錦標(biāo)賽一樣,它采用的是一種單一淘汰制,被淘汰的球隊(duì)是不排序的。這種賽制的優(yōu)勢在于它的線性時間。由于每場比賽正好淘汰一支隊(duì)伍,因此,要讓一支隊(duì)伍留到最后,一共需要n-1場比賽。這是一個線性數(shù)字。不足之處是,這種賽制只能決出第一名,無法給出名次表。
很多優(yōu)秀的算法,很容易在生活中找到案例,同時也可以把算法技巧用在生活和工作上。
書名為《算法之美–指導(dǎo)工作與生活的算法》
同時推薦一本《數(shù)據(jù)結(jié)構(gòu)與算法__Python語言描述_裘宗燕編著_北京:機(jī)械工業(yè)出版社》
我很少大范圍的推薦資料,知道什么是有用的,可以幫助自己少走很多彎路,需要的小伙伴,網(wǎng)盤自?。?br /> 鏈接: https://pan.baidu.com/s/1W8p4xXO7XaZiUxXgS9VjIQ 提取碼: qrej 復(fù)制這段內(nèi)容后打開百度網(wǎng)盤手機(jī)App,操作更方便哦
最后,感謝大家三連關(guān)注,支持一波。
文章版權(quán)歸作者所有,未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址:http://m.hztianpu.com/yun/121682.html
摘要:前言在開發(fā)技術(shù)和應(yīng)用市場完全成熟的今天,有人希望深耕技術(shù)打造出自己的一片天地,也有人想廣泛學(xué)習(xí)在程序員市場中游刃有余。而這本書上千的引用論文,給我指明了一條系統(tǒng)學(xué)習(xí)理論的明路。 ...
必須要看的前言 本文風(fēng)格:以??簡單易懂??的語言帶你徹底搞懂KNN,了解什么是有監(jiān)督學(xué)習(xí)算法。 認(rèn)真看完這篇文章,徹底了解KNN、了解監(jiān)督學(xué)習(xí)算法絕對是一樣很簡單的事情。 注:本篇文章非常詳細(xì),同時我也附加了Python代碼,歡迎收藏后慢慢閱讀。 目錄 必須要看的前言監(jiān)督學(xué)習(xí)算法KNN/K近鄰算法1 算法原理1.1 實(shí)現(xiàn)過程1.2 距離的確定 2 算法的優(yōu)缺點(diǎn)3 算法的變種3.1 變...
??歡迎訂閱《從實(shí)戰(zhàn)學(xué)python》專欄,用python實(shí)現(xiàn)爬蟲、辦公自動化、數(shù)據(jù)可視化、人工智能等各個方向的實(shí)戰(zhàn)案例,有趣又有用!?? 更多精品專欄簡介點(diǎn)這里 治愈生活的良方 就是保持對生活的熱愛 前言 哈嘍,大家好,我是一條。 每次和女朋友出去玩,拍照是必須的,天氣好還行,天氣要是不好,加上我這破手機(jī),那拍的簡直慘不忍睹,自己都不過去。 但是沒什么能難倒程序員的,為了不挨罵,連夜寫出去霧...
互聯(lián)網(wǎng)高速發(fā)展,隨著科技的進(jìn)步有一些崗位薪資出現(xiàn)了墊底的情況比如:生產(chǎn)制造、客服、行政等崗位。也有一些崗位薪資有了大幅度的增長:營銷/運(yùn)營、研發(fā)/開發(fā),以及IT相關(guān)的崗位。 那么對于一個應(yīng)屆畢業(yè)生,并非計算機(jī)專業(yè)的該如何進(jìn)入IT這個領(lǐng)域呢? 推薦你來學(xué)習(xí)軟件測試,首先軟件測試只有20%的代碼,對文科生來說是非常又好的。學(xué)習(xí)軟件測試的入行難度相對比開發(fā)壓力小很多。就算是你想要選擇在二線城市就業(yè),不想...
閱讀 2337·2021-09-30 09:48
閱讀 3693·2021-09-24 10:27
閱讀 1940·2021-09-22 15:32
閱讀 2101·2021-08-09 13:44
閱讀 3659·2019-08-30 15:55
閱讀 1113·2019-08-29 17:12
閱讀 2143·2019-08-29 17:05
閱讀 2985·2019-08-29 13:43