資料結構與演算法(下)01 by 隨機客

非正題
當初一時高興之下決定每個禮拜前往台大旁聽的決定，現在已經是第三個禮拜，想想也是覺得複雜了些(早上七點起來+來回60km機車)，但是現在想想，上這堂課是蠻值得的，一直都很想為這堂課寫一些blog note，但是，呃，苦無時間，原因很多，所以且戰且走吧:)，這還是我蠻常說的一句話。

---

2007/02/26 資料結構與演算法(下) 呂學一 投影片

這堂課主要講述的是隨機演算法(yen3註：跟隨機客有異曲同工之妙XD)，主要著重於兩個重點

• Randomized quick sort

sorting 乃萬古常青的演算法問題，quick sort更是在1960年代時被提出，在投影片的一開始複習quick sort的特性(標準的divide and conquer)與algorithm的運作方式(yen3補註：這中間有非常的漂亮動畫說明，考據指出，只用了powerpoint的內建功能)。

quick sort的時間最佳為O(n logn)，最糟為O(n^2)，這中間的效率在於pivot的選取，重點來了，怎麼選？當然，一般化的想法，選中位數，中位數的選取幾乎可以獨立成為一個演算法的課題(在簡報中提到許多paper都在選中位數，而這篇關鍵性的paper author幾乎都得了Turing Award XD)，證明出選中位數是linear time，於是隨機客在這邊丟出一個問題，是否在做quick sort的選取pivot時，一定要用到如此複雜的選中位數呢？

當然有其他解法，Randomized 選取pivot是一個解，隨機演算法本身的撰寫無難度可言，難的是，如何得知效率(time and space complexity)？亂數是否真的夠亂(yen3註：C library 下的rand() 是個眾所皆知的假隨機亂數)，經過證明，經過隨機選取的亂數當pivot，有一半的機率會達到最佳效率，也可以證明出O(n logn) 是成立的(隨機客將中間證明省略)


• Randomized maximum cut

掃黑的藝術(yen3註：XD)
給一個圖G，找出從A node 至B node能夠將最多edge切掉，但是也有一個問題，each node no more than 3 neighbors. 問題規定如題，求出最大切割的time complexity 也是O(c^n) c為constant ，n 為節點數...如果n 非常大，此題接近無解

Approximation Algorithms(近似演算法)現身啦，噹噹噹(近似演算法的哲學：放下對完全的堅持，往往就可以找到新的出路。知所進退，則近道矣。)在此問題上，使用隨機演算法選取node進行切割，則有機率是最佳解的一半(但是時間就是生出亂數的時間XD)，隨機近似演算法就變成一個很好的解法(yen3註：後面看不太懂，要再念書。)

對隨機演算法不要有一個誤解，無論input data為何，都不影響其效率，也就是說，對於best case和wroest case，隨機演算法皆保有同一個效率，並不因input改變，因此，沒有必要對所有可能的input 算出每一個時間複雜度，若是這樣子，此隨機演算法不成立。當然，隨機演算法也有其罩門，這世界上是否真的有亂數產生器？(Pseudo-random generator exists if and only if one-way function exists.)到目前為止沒有人知道有沒有，因為事實上證明出現有的亂數產生器都是有跡可循的，若是用C library 上的rand() ，照著一定公式所產生的亂數，也有演算法可以很大的機率猜出下一個會出現的數字是什麼(以bit的觀點)。在這也提到了P vs NP problem (列入Hilbert's 23 open questions)。

亂數沒有那麼好產生，也早就有人證明出依照現在所存的方法，所產生的亂數都是假隨機亂數(也就是有跡可循的亂數)，要能夠產生真正夠亂的亂數依舊是一個難題，世界上沒有一個公平的硬幣，所以就有了一個題外話的數學小證明，號稱20世紀最聰明的人von Neumann，提出了丟硬幣的方法(見投影片p.38)。用了簡單的機率，即得證。

---

有錯誤請盡量指正，謝謝:)

---
寫的好長好亂，下次我是不是該改成wiki..XD