計數一個有限集合與分析一個算法,都要求如實地處理「重複」。同一個委員會可以因成員排列次序不同而被重複計算多次;一個遞歸程式可以透過不同的調用多次求解同一個數學子問題。除以對稱因子與共用重複子問題是兩種不同的修正方式,但二者都始於準確辨識:計算把甚麼視為不同的對象。
動機
設有八名學生可供擔任三個職位。若職位是主席、秘書和司庫,則選出三名不同學生並分配職位是有序選擇。若只是組成一個三人委員會,則對成員重新排列並不產生新的委員會。兩個問題涉及同樣的人和同一個數字三,答案不同是因為所數的對象不同。
算法中的計數問題同樣應當說明其對象是函數、子集、字串還是執行過程。若一個雜湊函數把十一個鍵映射到四個桶中,則碰撞無可避免。這並不表示每個桶的大小相同,也不表示某一對特定的鍵發生碰撞,更不表示該雜湊函數實作得不好。計數界所證明的,僅是其量詞所陳述的內容。
遞推式則帶來另一種重複計算或遺漏計算的機會。合併排序做兩次規模為原來一半的遞歸調用;二分搜尋只繼續進入其中一半。兩者的深度相近,但每層的工作量不同。畫出遞歸樹並對各層求和,可以令這一區別一目了然,並解釋對數深度何時產生對數、線性或更大的總成本。
定義
定義 1.3.1
(函數及其類型)
函數 為其定義域 中的每個元素 恰好指派陪域 中的一個元素 。若相等的輸出蘊含相等的輸入,則稱其為單射;若陪域中每個元素都作為某個輸出出現,則稱其為滿射;兩者同時成立則稱為雙射。像 可以比指定的陪域小。保持同一指派而改變陪域,可能改變該函數是否為滿射。
定義 1.3.2
(階乘與二項式係數)
對非負整數 ,定義 ,且 。對整數 ,以 表示 元集合的 元子集的個數。由 個互不相同的元素構成的有序列表記住了第一項、第二項及其後各項; 元子集則只記住成員關係。有放回抽樣容許元素重複,因此其列表又是另一類對象。當 時,這個計數為零,我們定義 ;下文的階乘公式僅用於 。
定義 1.3.3
(漸近記號)
對於正整數上最終非負的函數, 表示存在常數 和 ,使得對一切 都有 。當 時記 ;當兩個界同時成立時記 。這些常數不依賴於 。這些是最終意義下的比較,因此有限多個較小的輸入可以另行處理。對這類界而言,底數為不同固定常數(大於一)的對數之間只相差一個常數倍。
定義 1.3.4
(遞推式與遞歸樹)
遞推式透過較小的自變量並配合初值來確定一個函數。對於成本遞推式,每一項都必須對應算法的某個具體部分:遞歸調用、合併工作或初始化。遞歸樹是一種記帳工具,其節點是調用的出現。若程式不使用記憶化而做了兩次調用,則即使兩個節點的輸入值相等,它們也代表兩次執行。
定理/命題
定理 1.3.5
(有序分配與子集)
若 且 ,其中 ,則從 到 的單射個數為 ,並且
從空集到任一固定集合恰有一個函數。對 ,從 元集合到 元集合的全部函數共有 個;若 ,則該計數為零。
定理 1.3.6
(鴿籠原理給出最大纖維的下界)
若把 個對象分配到 個盒子中,則至少有一個盒子至少收到 個對象。特別地,從一個有限集合到一個元素較少的集合,不可能存在單射。
定理 1.3.7
(由各層求和得到的平衡遞推式)
設 ,其中 ,並設 ,且對更大的此類輸入有 ,其中常數 ,,。則當 2 的冪增大時,
這些結論只針對所述的平衡遞推式。子問題規模不相等,或含有非多項式的額外工作時,需要重新分析。
證明思路
證明
(計算單射與子集)
要數單射的個數,先把定義域的元素按固定次序排列。第一個元素有 種可能的像,下一個有 種,第 個有 種,因為單射性禁止使用之前已用過的像。它們的乘積為 。當 時乘積為空,等於一,反映了唯一的空指派。若容許重複,則每個定義域元素都有 種選擇,對 得到 。
每個由 個互不相同元素構成的有序列表,在忽略次序後決定一個 元子集。每個這樣的子集恰有 種排列,因此這一「忘記次序」映射的所有纖維大小均為 。按其底層子集對有序列表分類,再除以這個共同的纖維大小,即證明了二項式公式。纖維大小相等正是除法的依據;當不同對象有不同數量的描述時,一般不能隨意用某個方便的數去除一個計數。
證明
(鴿籠界)
對於鴿籠界,令 。若每個盒子至多含 個對象,則總數至多為 ,這由定義性質 得出,與對象總數矛盾。 的情形無妨:每個盒子都含零個,符合所聲稱的下界零。當 時,該界給出某個盒子中至少有兩個對象,與單射性矛盾。
證明
(按層對平衡遞推式求和)
對於遞推式,樹的高度為 。在第 層有 個節點,每個的規模為 ,因此它們的非遞歸工作總量為 。共有 個葉子,每個的成本為 。當 為整數時,這確實是一棵調用樹;當 不是整數時,同樣的展開是一個代數恆等式。無論哪種詮釋,都有
令 。若 ,則對 ,幾何和介乎一與 之間。葉子項 ,因此總量為 。若 ,則和為 ,葉子項為 ;由於 ,當 增大時總量為 。
若 ,則和 對大的 為 。乘以 得 。葉子項具有同樣的量級,證明完畢。請留意,葉子的成本參與了最終結果,而不是在分析中消失。
證明透視
深度並未計入所有調用
對數高度說明的是:沿單獨一條從根到葉的鏈,一個輸入可以被減半多少次。把一個節點的工作量乘以高度,只有在同時計入所有其他節點時才有效。層因子 提供了所缺少的重數。在平衡遞推式中,幾何比告訴我們工作量是集中在根附近、按層均勻分布,還是集中在葉子附近。
帕斯卡(Pascal)恆等式給出第二種子集計數:對 ,有 。固定一個元素。不含它的子集由第一項計數;含有它的子集在刪去它之後,對應於其餘集合的 元子集。兩種情形不相交且窮盡。邊界計數 隨後支撐起一張動態規劃表。不使用表的直接遞歸會反覆計算相同的參數對;遞推式正確與實作高效是兩項不同的成就。
例題詳解
例題 1.3.8
(三個職位還是一個委員會)
從八名學生中選出三名不同的學生分別擔任主席、秘書和司庫,共有 種可能。組成一個三人委員會則有 種,因為每個委員會有六種排列。若容許同一名學生擔任多個職位,則職位分配共有 種。這些答案沒有哪一個本質上更正確:它們數的是不同的指定對象。
例題 1.3.9
(強制碰撞究竟保證了甚麼)
十一個互不相同的鍵被映射到四個桶中。鴿籠界保證存在一個桶至少含 個鍵。負載 顯示不可能有更大的普遍下界。該定理並不能事先指出是哪個桶,也不能指出哪一對鍵發生碰撞。它同樣不蘊含每個桶至少有兩個鍵:負載 也符合分配規則。
例題 1.3.10
(更大的分支因子改變成本)
對於二的冪上的 ,,第 層的成本為 ,並且有 個葉子。求和得 。當 時,中間成本為 ,,。樹的高度為三,但其總工作量並非 。這裏 ,該定理正確地給出 。
作為比較,一次規模減半、工作量為常數的遞歸調用有 ,因此成本是對數的。兩次規模減半的調用並伴隨線性的合併工作,有 ,因此成本為 ,如合併排序。四次規模減半的調用並伴隨線性的合併工作,則給出上面的二次例子。只有在確認實際算法確實做了所述調用並產生所述局部成本之後,這些比較才有意義。
並非每個遞推式都是平衡的。對於固定常數 與 ,設 和 ,展開得 。把減半型定理套用到這個遞推式上,會悄悄改變算法本身。這種線性深度的模式描述的是,例如,一個遞歸劃分程序反覆只留下一個比之前小一的子問題,且每次調用的工作量為線性。平均情況的平衡直覺不能取代最壞情況的遞推式。
由迴圈執行次數推導增長界
給出成本界之前,要先說明輸入規模和計數的操作。設陣列長為 ,索引由零開始。一個程序檢查每對位置:對 ,依次取 ,比較兩個位置的元素。當 時,內層範圍為空。令 只計元素比較次數; 時沒有比較。
固定 後, 有 個取值。因此
最後的等式可這樣證明:把這個和分別按升序和降序寫出,逐項相加。每一對的和都是 ,共有 對,所以原和的兩倍為 。 和 時比較次數均為零,公式仍成立。這個程序恰好把每一對不同位置計算一次:較小索引是 ,較大索引是 。兩個位置的值相等,也不代表這兩個位置相同。
對每個整數 ,有 ,所以
這些固定常數同時給出上界和下界,證明 。若每次訪問的迴圈控制操作耗時為常數,初始化亦需常數時間,那麼附加的 工作不改變總運行時間的 增長。這裏假定訪問和比較元素均耗常數時間;例如元素是長字串時,一次比較本身可能依賴字串長度。
證明透視
巢狀迴圈需要求和,不能只猜次數
兩層迴圈並不自動意味著內層迴圈體執行 次。這裏內層長度依次是 ,並非每次都是 。精確求和同時提供上、下界。如果每個外層索引只對應一次內層迭代,次數便會是線性的。
例題 1.3.11
(搜尋提早停止會帶來甚麼變化?)
順序搜尋由左至右把目標與陣列元素比較,找到第一個相符元素就停止;如果沒有匹配,則比較至末尾。長度為 的輸入中,若第一個匹配在由一開始計數的位置 ,元素比較次數為 ;若目標不存在,次數為 。當 時,在所有陣列和目標中,最好情況是一開始就匹配,次數為一;最壞情況是目標不存在,次數為 。因此最好情況的比較次數為 ,最壞情況為 。空陣列的兩種次數都是零。
最壞情況函數的上界亦約束同規模的每一個具體輸入;一個有利輸入的成本卻不能約束所有其他輸入。討論平均情況還必須指定輸入的概率分布,最好和最壞情況都不能取代這個條件。
快速檢查
(另一個程序取 ,對每個 再取 ,每次訪問一次。共訪問多少次,增長階是甚麼?)
解答 · 答案
內層迴圈體執行 次,總數為 ; 時為零。當 時,它介乎 和 之間,故為 。兩段迴圈枚舉的位置對並不相同:把第一段中每個嚴格非對角位置對的座標交換,恰好得到第二段的嚴格非對角位置對。第二段還對每個 包含一個對角位置對,因此計數多 。
常見錯誤
常見錯誤
(定義域與陪域屬於函數的一部分)
定義域和陪域是函數規格的一部分。從實數到實數的指派 不是滿射,但同一指派到非負實數則是滿射。它仍然不是單射,因為一與負一有相同的像。這些陳述並不矛盾,因為單射性與滿射性問的是不同的問題。
常見錯誤
(把「選三個」讀成與次序無關)
不要把「選三個」這一說法當作次序無關的證據。是否讓被選對象擔任不同的角色,取決於前後的任務。同樣,重複可能被單射性禁止,也可能被輸入模型容許;只有在明確這些選擇之後,公式才有用。
反例模式
並非所有對稱性都產生相同數量的描述
有序列表 、 和 描述的是同一個多重集,共有三種排列,而 有六種。因此,把所有長度為三的列表都除以 ,並不能正確地數出多重集的個數。子集公式之所以成立,是因為其元素互異的假設令每條纖維大小相同。
常見錯誤
(上界不等於精確的增長階)
上界並不表示成本恰好是二次的,甚至不表示二次增長是必要的。線性函數同樣是 。要得到 結論,需要匹配的下界,並且要說明分析針對的是最壞情況、平均情況還是某個受限的輸入族。
總結
計數始於對象:任意函數、單射和子集有不同的重數。均勻的纖維大小為對有序計數做除法提供依據;當分配擁擠時,鴿籠原理給出最大纖維的界。遞推式分析同樣是數出所有調用的出現並對它們的工作求和。明確的初值、分支因子和成本模型,可以避免一個看似正確的公式描述了錯誤的問題。
練習
快速檢查
(從一個四元集合到一個三元集合有多少個函數?其中有多少個是單射?請在不使用負階乘的情況下解釋這兩個答案。)
解答 · 答案
四個輸入中的每一個都有三種獨立的指派選擇,因此共有 個函數。單射不存在:四個互不相同的輸入不可能在三個輸出值上不發生碰撞。取 的單射公式不適用於 ;此時由鴿籠論證直接處理。
快速檢查
(證明:在固定的帶標號 個頂點的集合上,簡單無向圖的個數為 。)
解答 · 答案
簡單無向邊是由兩個不同頂點構成的無序對,這樣的對共有 個。每一對要麼出現,要麼不出現,且與其他對的選擇相互獨立。這在帶標號的簡單圖與可能邊集的子集之間建立了雙射,從而得到所述的二的冪。假設已排除環和有向邊。
快速檢查
(計算 ,並就這一具體計數解釋帕斯卡恆等式。)
解答 · 答案
該計數為 。固定十個元素中的一個。不含它的四元子集有 個,含有它的有 個。它們的不交併給出 。
快速檢查
( 是否屬於 ?是否屬於 ?請由最終不等式論證這兩個結論。)
解答 · 答案
對正整數 ,有 ,故 ,於是得到第一個上界。對於第二個, 無界:對於任何擬取的常數 ,整數 都違反 。因此不存在最終成立的線性上界。
練習 1.3.12
(分析二的冪上的 ,。給出精確表達式以及漸近界。)
核心
解答(3)
- 1
按層對工作量求和
在第 層有 個規模為 的節點,所以該層的成本為 。
- 2
加上各層與葉子
取 ,並有 片成本為一的葉子,則 ,與 相符。
- 3
讀出增長階
因此 ;根層的二次工作量已經給出下界。