推 jeremy4849:X所以有點像單淘汰的感覺 02/19 18:51
推 entryword:我覺得這個比較次數算錯了 一邊比了另一遍就不用比了 02/20 01:36
→ entryword:比較次數是說decision tree上一條路徑最多要比幾次 02/20 01:37
→ entryword:所以比三次會有六種結果 02/20 01:38
推 a5120265:我還是比較贊成2^k次@@" 02/21 20:58
比一次
比較
/ \
Y / \ N
/ \
結果1 結果2
比兩次
比較 比較
/ \ / \
Y / \ N Y / \ N
/ \ / \
比較 結果3 or 結果1 比較
/ \ / \
Y / \ N Y / \ N
/ \ / \
結果1 結果2 結果2 結果3
比三次
比較
/ \
/ \
Y / \ N
/ \
/ \
比較 比較
/ \ / \
Y / \ N Y / \ N
/ \ / \
結果1 結果2 結果3 結果4
單純暴力法 ... XD
接下來用數學歸納法應該可以推得 k+1
※ 引述《jeremy4849 (yang)》之銘言：
: 1. Assume that the elements are pairwise distinct. Answer the following questions on sorting algorithms.
: (2)A single comparison between two elements can distinguish up to 2 permutations. How many permutations can be distinguished using k comparisons?
: 我的答案：(k+1)!
: 不知道這題的意思是什麼，我的假設是在k+1個數之下做 k comparisons，如果有3個數做2 comparisons 應該可以有 3!個組合，因為每種組合似乎都可以用最多兩次交換就可以得到。
: 這題之前有人討論過，看完還是不解，不知道大家的想法如何。感謝！
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.224.40.173