前言

文章摘抄至《演算法之美》，附帶了Python模擬，

不久前，我去觀看草地網球錦標賽，一位十分沮喪的運動員引起了我對球賽目前采用的名次確定方法的注意，這位運動員在比賽中早早落敗，因此徹底失去了獲得獎牌的機會，令他感到屈辱的是，獲得第二名的是他知道的一名遠不如自己的運動員，

在這里插入圖片描述

普通觀眾可能會把這種“哀嘆”歸咎于失敗的痛苦，但道奇森并不是一個同情心泛濫的人，他是牛津大學數學系講師，因此，在聽到運動員的抱怨之后，他決定對體育賽事展開深入調查，道奇森不僅僅是一個數學家（其實他幾乎不記得自己是從事數學研究的），現在，反而是他的筆名——劉易斯·卡羅爾更加廣為人知，他以這個筆名寫出了《愛麗絲漫游奇境記》以及大量其他深受歡迎的文學作品，他還將他的數學知識與文學天賦相結合，完成了一篇知名度略低的文章——《草地網球錦標賽：正確的名次確定方法以及現行方法辨誤》，

道奇森針對的是單一淘汰賽，在這種賽制下，運動員兩兩對決，只要輸掉一場比賽，就會被淘汰出局，道奇森的理由非常有說服力，他認為，貨真價實的第二名有可能是被第一名淘汰的任何人，而不一定是最后才被淘汰的那名運動員，

在這里插入圖片描述

直白地說，銀牌是一種假象，“作為一個數學事實，”他繼續寫道，“實力排第二位的運動員獲得應得名次的機會只有16/31，而最優秀的4名運動員獲得與實力相稱名次的機會非常小，發生的概率為1/12！”

這里可以借助Python演示一下（語言不重要，可以改成自己熟悉的，）

import copy
import random

class 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=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名后結束
    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 += 1
            break
print(isNO2count)

== 看輸出結果，我們很容易發現，結果在22-28%之間徘徊， ==
而只有把if v.name==‘No.3’:的No.3改成No.1才會是100%，

盡管道奇森的文章犀利有力，卻沒有對草地網球產生任何影響，他提出應該采取三敗淘汰制（根據這種賽制，擊敗過你的運動員如果落敗，也有可能導致你隨之出局），但是這個提議根本沒有人理會，不過，雖然道奇森的解決方案實施起來有很大的難度，但是他在這個問題上的看法仍然是有道理的，（可惜的是，至今為止，在單淘汰賽中，仍然會頒發銀牌，）不過，道奇森的邏輯還給我們帶來了一個更加深刻的認識，我們人類不僅會對資料、財產進行排序，還會把我們自己變成排序物件，

世界杯、奧運會、美國全國大學體育協會（NCAA）、美國全國橄欖球聯盟（NFL）、美國全國曲棍球聯合會（NHL）、美國職業籃球聯賽（NBA）和美國職業棒球大聯盟（MLB），所有這些賽事都毫無疑問地使用了排序程式，利用賽季、排位賽和季后賽等演算法排出先后關系，體育運動中的回圈賽制就利用了演算法，如果一共有n支運動隊，那么每支運動隊最終都要和其余n-1支隊伍比賽，這種賽制雖然可以說是最全面的，但也最費時費力，

讓每一支運動隊都與其他所有隊伍比賽，就像在晚宴上讓客人兩兩擁抱一樣，最侄訓需要可怕的O（n²）次角逐，排位賽（在羽毛球、英式壁球和美式壁球等體育專案中比較常見）對運動員進行線性排序，每個球員都可以直接鏌馀在前面一位的球員發起挑戰，如果獲勝，則交換排位，排位賽就相當于運動場上的冒泡排序，因此也是平方排序，需要O（n²）場比賽才能得到穩定的排名，

到這里就要提到演算法的兩個基礎概念：

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場比賽，這是一個線性數字，不足之處是，這種賽制只能決出第一名，無法給出名次表，