本系列博客習(xí)題來自《算法(第四版)》，算是本人的讀書筆記艇棕，如果有人在讀這本書的，歡迎大家多多交流串塑。為了方便討論沼琉，本人新建了一個微信群(算法交流)，想要加入的桩匪，請?zhí)砑游业奈⑿盘枺簔hujinhui207407 謝謝打瘪。另外，本人的個人博客 http://www.kyson.cn 也在不停的更新中傻昙，歡迎一起討論
知識點
- 路徑壓縮
題目
1.5.12 使用路徑壓縮的 quick-union 算法闺骚。根據(jù)路徑壓縮修改 quick-union 算法（請見 1.5.2.3 節(jié)），在 find() 方法中添加一個循環(huán)來將從 p 到根節(jié)點的路徑上的每個觸點都連接到根節(jié)點妆档。給出一列輸入僻爽，使該方法能夠產(chǎn)生一條長度為 4 的路徑。注意：該算法的所有操作的均攤成本已知為對數(shù)級別贾惦。這種改變會對性能產(chǎn)生怎樣的影響胸梆？
1.5.12 Quick-union with path compression. Modify quick-union (page 224) to include path compression, by adding a loop to union() that links every site on the paths from p and q to the roots of their trees to the root of the new tree. Give a sequence of input pairs that causes this method to produce a path of length 4. Note : The amortized cost per operation for this algorithm is known to be logarithmic.
分析
路徑壓縮在書中的敘述在英文版231頁敦捧，如下：
答案
題目
1.5.13 使用路徑壓縮的加權(quán) quick-union 算法。修改加權(quán) quick-union 算法（算法 1.5）碰镜，實現(xiàn)如練習(xí) 1.5.12 所述的路徑壓縮兢卵。給出一列輸入，使該方法能產(chǎn)生一棵高度為 4 的樹绪颖。注意：該算法的所有操作的均攤成本已知被限制在反 Ackermann 函數(shù)的范圍之內(nèi)秽荤，且對于實際應(yīng)用中可能出現(xiàn)的所有 N 值均小于 5。
1.5.13 Weighted quick-union with path compression. Modify weighted quick-union (Algorithm 1.5) to implement path compression, as described in Exercise 1.5.12. Give a sequence of input pairs that causes this method to produce a tree of height 4. Note : The amortized cost per operation for this algorithm is known to be bounded by a function known as the inverse Ackermann function and is less than 5 for any conceivable practical value of N.
分析
題目中的Ackermann柠横，相信大家不一定熟悉窃款，這里我找了些資料：
威廉·阿克曼
威廉·阿克曼，德國數(shù)學(xué)家牍氛，最著名的成果是計算理論的重要例子阿克曼函數(shù)雁乡。
阿克曼函數(shù)
阿克曼函數(shù)（Ackermann）是非原始遞歸函數(shù)的例子。它需要兩個自然數(shù)作為輸入值糜俗，輸出一個自然數(shù)踱稍。它的輸出值增長速度非常高，僅是對于(4,3)的輸出已大得不能準確計算悠抹。
Ackermann函數(shù)定義如下：
若m=0珠月，返回n+1。
若m>0且n=0楔敌，返回Ackermann(m-1,1)啤挎。
若m>0且n>0，返回Ackermann(m-1,Ackermann(m,n-1))卵凑。
單變量反Ackermann函數(shù)（簡稱反Ackermann函數(shù)）
α(x)定義為最大的整數(shù)m使得Ackermann(m,m)≤x庆聘。從上面的討論中可以看到，因為Ackermann函數(shù)的增長很快勺卢，所以其反函數(shù)α(x)的增長是非常慢的伙判，對所有在實際問題中有意義的x，α(x)≤4黑忱，所以在算法時間復(fù)雜度分析等問題中宴抚，可以把α(x)看成常數(shù)。
α(x)出現(xiàn)在使用了按秩合并和路徑壓縮的并查集算法的時間復(fù)雜度中甫煞。
我相信就算我貼了這么多菇曲，很多人還是對Ackermann函數(shù)一知半解，那我們這里再解釋一下抚吠。首先我們要了解Ackermann函數(shù)是“非原始遞歸函數(shù)”常潮。那遞歸大家都知道，那什么叫做“原始遞歸”和“非原始遞歸”呢楷力。
