大家可以到作業網站下載解答:
http://www.csie.ntu.edu.tw/~r95121/algo/
第二題證明lower bound
大家都會用畫full tree的方式來說明如何找最大和第二大
但這只是一種可以在n-2+ceil(lgn)時間內解決問題的"演算法"
最好先證明所有找最大和第二大的演算法都對應到某種樹狀結構
且worst case lower bound恰好發生在full tree上面
(如同證明comparison based sorting的lower bound一樣)
在解答當中 我們利用了另一種證明方法 -- adversary argument
也附加了一個doc檔 解釋何謂adversary argument
希望大家對於證明lower bound的方式 能有更多的了解
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.30.84
※ 編輯: kchiu 來自: 140.112.30.84 (11/16 16:24)