※ 引述《forris (喬巴)》之銘言：
: 標題: [問題] 搜尋排序
: 時間: Tue Jul 1 01:24:00 2008
:
: n 個元素存於陣列 L 中排序，在插入排序法中，若決定插入元素 L[i] 的位置利用
: 二分搜尋法，在 L[1] <= L[2] <= ..... <= L[i] 中找出適當位置
: (1) 最壞情形下，此一修改的插入排序元素比較總數為何？
:
: 是 O(n^2) ? O(n) ? 還是 O(log n) ?
:
:
: (2) 最壞情形下，共需元素搬動總數為何？
:
: 是 n(n-1)/2 ?
:
: --
: ※ 發信站: 批踢踢實業坊(ptt.cc)
: ◆ From: 218.173.242.32
: 推 future1234:用Decision tree求最多比較次數: 取 (log2(N+1))上限 07/01 14:16
: ※ forris:轉錄至看板 Examination 07/01 20:39
: 推 future1234:Binary Insertion Sort: 07/02 03:07
: → future1234:(1)原本比較次數: O(N) 採Binary Search降到 O(logN) 07/02 03:08
我覺得還是用回文的說明比較清楚
原本插入排序比較次數是 O(N), 但是用二元搜尋法模擬插入排序法，在最壞情形下，
是退化成循序搜尋法。
所以比較次數會變成 O(log n) ?
: → future1234:(2)因為Binary Search本身仍採Array儲存資料 07/02 03:10
: → future1234:因此,元素搬移次數為 O(N) 07/02 03:10
: → future1234:不過,Linear Insertion Sort就可以把搬移次數降到O(1) 07/02 03:13
最壞情形下，是反向排序，共搬動元素總數
不是 n(n-1)/2 次嗎?
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.173.241.5