找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

12
返回列表 发新帖
楼主: maple10001
收起左侧

[Amazon] A家遇到的一道数组排序题

[复制链接]

8

主题

2

精华

232

积分

高级会员

Rank: 3Rank: 3

积分
232
发表于 12-3-2014 02:22 AM | 显示全部楼层
Use quick select to find the median by O(n) and split the array into halves. Then do a merge on two halves by O(n).

1

主题

1

精华

212

积分

高级会员

Rank: 3Rank: 3

积分
212
发表于 12-3-2014 02:21 PM | 显示全部楼层
tmp2013 发表于 12-3-2014 02:22 AM
" a1 r& e  }' P! q0 n/ j+ g% UUse quick select to find the median by O(n) and split the array into halves. Then do a merge on two  ...
; C$ v6 y$ f7 t7 o, _
quickselect最差不是O(n)

8

主题

2

精华

232

积分

高级会员

Rank: 3Rank: 3

积分
232
发表于 12-3-2014 07:50 PM | 显示全部楼层
changhaz 发表于 12-3-2014 02:21 PM
) U# m+ d: ^7 Y! F* iquickselect最差不是O(n)

0 C; o% s, t! x0 T6 DGlad to discuss, the worst case for quickselect is O(n^2). It occurs when choosing the first element as pivot and searching the maximum in a sorted array, for example. However, it's linear to search a median with a random pivot by at most 4n comparison in a worst case. Proofs can be googled with "Blum-style analysis of Quick Select". Frankly speaking, I didn't read through the proof
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表