I thought it is about the Corona virus
我發現 codewriting 比 debug 簡單＝＝
我是一個只知道 List 跟 compare 的小廢物
??????????????????????????????????????
類似可以證明 Comparison sort 的最佳解是 O(n log n) 一樣
我在沒有 code 的情形下可以證明 Comparison sort 的最佳解釋 O(n log n)
一個長度為 n 的 List 有 n! 種排列可能
每次 compare 兩個 element 我可以得到 true 或 false
Comparison sort 這個詞本身就有算法ㄉ含義ㄌㄅ
我覺得 Comparison sort 沒有具體說出算法ㄚ
Big O 不 care 是 log_2 還 log_3 ㄅ
而且我覺得 Comparison sort 這個詞告訴你的是你只能用 Compare
就是說 假設一個 List 裡的元素能用 compare
其他的排序還有 bucket 之類的
跟一般什麼 quick sort merge sort 那種ㄉ排序不太一樣
不是後這也不是我發明的證法 你去網路上找找到的都是這個啊
不是啊你算數學求最大值的時候也不一定順便求出x要代多少啊
那我在最理想的情況不是就可以把可能的組合當中刪去一半ㄇ
數學上是
Sigma(k) for k from 0 to n
那個 nlog n 是說不可能做的比 nlog n 好，假如能夠做的比 n log n 好，那就會有些情形不可能分出來這樣?
對於一個長度為 n 的陣列 有 n! 種排序
我們取 a, b 出來排序
要馬是 a 大要馬是 b 大（等號不考慮）
其中一定有一種可能性數量 >= n!
/2
假設我們每次排序的運氣都差到爆 留下了最多可能性的那種
這次排序完留下了 >= n!
/2 種可能性
那麼下一次就會留下 >= n!
/4 種可能性
[2,1,3]好了
[1,2,3]
[1,3,2]
[2,1,3]
[2,3,1]
[3,1,2]
[3,2,1]
[1,2,3]
[1,3,2]
[3,1,2]
[2,1,3]
[2,3,1]
[3,2,1]
你現在就知道怎麼做了啊 這樣算不算先知道算法才能證最佳複雜度
comp sort 一定是 2 elem 去 comp 拿到一個 binary result
你可以把 comp sort 本身想像成一個抽象類別
比較排序的定義就是
用 bool func(T a, T b) 來決定 a, b 誰在前面
清大課程都改成用 RISC V 做課程範例ㄌ(?
計算機結構、編譯器都是
問ㄍ
PVE上裝BSD的話OS type要選哪個?
others?
我是裝pfsense啦
官方doc寫說選other 但那是超舊版的PVE
然後我在別的地方看到這個說法
pfSense inherits excellent support for KVM from FreeBSD, so Proxmox can simply consider it to be Linux
@seadog007 認為 @da21510 的意思是： 距離比較遠耶
@da21510 認為 @seadog007 的意思是： 會啦
又是這個話題嗎== comparision-based sorting algorithms performs at least Omega(n log n) comparisons for its worst case....
However, non-comparison-based sorting algorithms can have a worst case time complexity better than O(n log n)
The proof is simple: Consider a decision tree where each node represents a comparison and thus has two children (either a<b or b<=a). The leaves represent the sorted array (sequences).
Clearly, such a binary decision tree can at most have 2^h leaves given height h. But then, the tree needs to have n! such leaves to sort a n-item array
by some simplification you get on its worst input, it needs to perform Omega(n log n) comparisons
Yes this is the same idea as mine
Best case scenario: you pruned half the solution space
Actually, there are subtle issues here. We are trying to deal with the worst input possible. It is possible that you discard more than half the choices for any given steps, but this argument does not account for the worst input
關於programming/cs/whatever
這裏有個更強的結果： average-case is also Omega(n log n)
n!種排列（假設每個元素都相異
每次比較必有a<b or a>b
可能的排列數會/2
General Availability: 21 May 2014