作者forris (乔巴)
看板TransCSI
标题Re: [问题] 搜寻排序
时间Thu Jul 3 02:12:11 2008
※ 引述《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