→ ybite:7(f)：鴿籠原理問題。引述黃子嘉離散教材的證法： 01/27 22:31
→ ybite:假設x_k和y_k表示第k個數開始最長的遞增/遞減序列長度 01/27 22:31
→ ybite:以反證法出發，假設遞增遞減序列最長只到n 01/27 22:32
→ ybite:那(x_k, y_k)最多只有n^2個組合，但因為有n^2+1個數字 01/27 22:33
→ ybite:一定可以找到不相等的i,j使(x_i,y_i)=(x_j,y_j) 01/27 22:33
→ ybite:可推得(x_i>x_j or y_i>y_j)，造成矛盾。 01/27 22:34
→ ybite:6(a)詳細希望 Orz 01/27 22:34
→ aoqq12:6(a) 他應該是問說 排序好的array 元素是不是很難找尋 01/27 23:16
→ aoqq12:答案就是false嚕 01/27 23:16
→ ai305428d:我是覺得false啦,如果裡面data的需求不一 01/27 23:27
→ ai305428d:但題目有講"Are equally likely to be requested" 01/27 23:30
→ ai305428d:講錯了..覺得是true 01/27 23:30
→ aoqq12:能舉例嗎? 01/27 23:38
→ ai305428d:如果對每個data需求不同,不是可以把比較常用的放在陣列 01/27 23:43
→ ai305428d:前面節省search時間嗎? 01/27 23:43
→ ai305428d:可是這題最後加上那段equally.... 01/27 23:45