Messages from June 2019

對

包 < 剪 剪 < 鎚 鎚 < 包

先挑兩個，隨便抓一個 那就有兩個插入的選擇 (用三元比較，可以就插入) 在隨便選一個 現在有三個插入選擇 (用三元比較，可以就插入) and so on..

但是這是最快的嗎

至少可排w

cyclic的話要改一下

我們可以先想想看他的 sort(cmp) 的那個 cmp 會長什麼樣子

S x S x S -> ?

我覺得應該也是 {1, 0, -1}

1 代表 a > b > c 0 代表可能有相等的 -1 代表 a < b < c

然後我們試著用資訊理論來求出他的理論最低複雜度ㄅ

.

https://www.quora.com/Why-is-the-%CE%A9-n-log-n-lower-bound-on-comparison-sorting-algorithms-called-the-information-theoretic-limit 這是在一般的 sort 為什麼最低 O(n log n ) 的解釋

先用 True 或 False 好了

假設有n個元素，在還沒開始排序前，總共有 n! / n 種可能

排完之後只有 1 種可能

這時候假設環狀不管怎麼轉都是同種

所以會是 O(k log k) where k = n-1

宏觀上來說跟一般的 sort 時間複雜度差不多

jq 潔癖