logo
Redian新闻
>未名空间
>JobHunting - 待字闺中
>
备考google onsite, 讨论堆排序的时间复杂度
avatar
备考google onsite, 讨论堆排序的时间复杂度# JobHunting - 待字闺中
s*t
1 楼
堆排序算法如下
HEAPSORT(A)
1 BUILD-MAX-HEAP(A)
2 for i = A.size downto 2
3 exchange A[1] with A[i]
4 A.size = A.size - 1
5 MAX-HEAPIFY(A, 1)
算法书上说
1 BUILD-MAX-HEAP(A) 的时间复杂度为 O(N)
5 MAX-HEAPIFY(A, 1) 的时间复杂度为 O(lg N), N 为当时 A 的长度
那么, 整个算法的时间复杂度是
O(N) + O(lg(N-1)) + O(lg(N-2)) + ... O(1)
= O(N + lg(N-1) + lg(N-2) + ... 1)
= O(N + lg(N-1)!)
= O(lgN!)
比快速排序的 O(NlgN) = O(lg(N^N)) 还要快?
迷惑了,求大牛指点.
avatar
O*i
2 楼
N * logN = log(N^N)貌似不对？
另外，说基于比较的排序下界是N*logN,
就是先得到总共有N!的排列方式，然后用到了决策树，高度就是
log(N!)
然后用了什么斯托林公式还是积分图，得到
log(N!)大致相当于N * logN

【在 s*****t 的大作中提到】
: 堆排序算法如下
: HEAPSORT(A)
: 1 BUILD-MAX-HEAP(A)
: 2 for i = A.size downto 2
: 3 exchange A[1] with A[i]
: 4 A.size = A.size - 1
: 5 MAX-HEAPIFY(A, 1)
: 算法书上说
: 1 BUILD-MAX-HEAP(A) 的时间复杂度为 O(N)
: 5 MAX-HEAPIFY(A, 1) 的时间复杂度为 O(lg N), N 为当时 A 的长度
avatar
p*2
3 楼

应该是nlogn
每插入一个是logn的复杂度，一共有n个。

【在 s*****t 的大作中提到】
: 堆排序算法如下
: HEAPSORT(A)
: 1 BUILD-MAX-HEAP(A)
: 2 for i = A.size downto 2
: 3 exchange A[1] with A[i]
: 4 A.size = A.size - 1
: 5 MAX-HEAPIFY(A, 1)
: 算法书上说
: 1 BUILD-MAX-HEAP(A) 的时间复杂度为 O(N)
: 5 MAX-HEAPIFY(A, 1) 的时间复杂度为 O(lg N), N 为当时 A 的长度
avatar
l*b
4 楼
log (n!)本来就和 n log(n)是同阶的呀，有什么问题？
heapsort本来速度就和quicksort差不多， quicksort的hidden factor小一点，
locality好一点吧

【在 s*****t 的大作中提到】
: 堆排序算法如下
: HEAPSORT(A)
: 1 BUILD-MAX-HEAP(A)
: 2 for i = A.size downto 2
: 3 exchange A[1] with A[i]
: 4 A.size = A.size - 1
: 5 MAX-HEAPIFY(A, 1)
: 算法书上说
: 1 BUILD-MAX-HEAP(A) 的时间复杂度为 O(N)
: 5 MAX-HEAPIFY(A, 1) 的时间复杂度为 O(lg N), N 为当时 A 的长度
avatar
l*b
5 楼
你自己积分一下就出来了，不需要用公式
log (n!) ~ int_1^n log(x) = n log(n) - n

【在 O******i 的大作中提到】
: N * logN = log(N^N)貌似不对？
: 另外，说基于比较的排序下界是N*logN,
: 就是先得到总共有N!的排列方式，然后用到了决策树，高度就是
: log(N!)
: 然后用了什么斯托林公式还是积分图，得到
: log(N!)大致相当于N * logN
avatar
f*e
6 楼
估计是本科数学学得不深，不知道什么是sterling公式，不过CLRS的附录里有，所以肯
定是附录也没有读。对初学者，CLRS要像圣经样的读:-);

【在 l*******b 的大作中提到】
: log (n!)本来就和 n log(n)是同阶的呀，有什么问题？
: heapsort本来速度就和quicksort差不多， quicksort的hidden factor小一点，
: locality好一点吧
avatar
l*b
7 楼
sterling公式推到最精确的那一形式还有点难的。不过估计log(n!)这个用积分快

【在 f*****e 的大作中提到】
: 估计是本科数学学得不深，不知道什么是sterling公式，不过CLRS的附录里有，所以肯
: 定是附录也没有读。对初学者，CLRS要像圣经样的读:-);
avatar
w*x
8 楼

靠， 那不得读两年？？？

【在 f*****e 的大作中提到】
: 估计是本科数学学得不深，不知道什么是sterling公式，不过CLRS的附录里有，所以肯
: 定是附录也没有读。对初学者，CLRS要像圣经样的读:-);
avatar
f*e
9 楼
大牛用不了那么长时间吧。好好读一遍总的花的时间可能会少一些。

【在 w****x 的大作中提到】
:
: 靠， 那不得读两年？？？
avatar
l*b
10 楼
这书好玩呀，要是老早学计算机，看一年也值了。现在没机会仔细看了，看多少算多少
吧，唉

【在 w****x 的大作中提到】
:
: 靠， 那不得读两年？？？
avatar
s*t
11 楼
明白了, 谢谢大牛们
avatar
g*e
12 楼
上班半年 已经搞不清什么是堆排序了
avatar
p*2
13 楼

你这次休假leetcode做了几遍了？

【在 g*********e 的大作中提到】
: 上班半年 已经搞不清什么是堆排序了
avatar
s*t
14 楼
明白了, 谢谢大牛们
avatar
M*u
15 楼
build-max-heap并不是全部排序

【在 s*****t 的大作中提到】
: 堆排序算法如下
: HEAPSORT(A)
: 1 BUILD-MAX-HEAP(A)
: 2 for i = A.size downto 2
: 3 exchange A[1] with A[i]
: 4 A.size = A.size - 1
: 5 MAX-HEAPIFY(A, 1)
: 算法书上说
: 1 BUILD-MAX-HEAP(A) 的时间复杂度为 O(N)
: 5 MAX-HEAPIFY(A, 1) 的时间复杂度为 O(lg N), N 为当时 A 的长度
avatar
l*a
16 楼
有些人没看过CLRS也有goog的offer
有些人学了几个学期也没有goog的offer

【在 l*******b 的大作中提到】
: 这书好玩呀，要是老早学计算机，看一年也值了。现在没机会仔细看了，看多少算多少
: 吧，唉
avatar
l*b
17 楼
不和别人比，自己乐呵，能填饱肚子就成了。哈哈

【在 l*****a 的大作中提到】
: 有些人没看过CLRS也有goog的offer
: 有些人学了几个学期也没有goog的offer
相关阅读
Amazon data scientist 面试内容？我来说一下我朋友遇到的倒霉事 (转载)有没有刷题刷的不错的了同学？netflix怎么进？非要refer？还是非要手上有flag的offer？现在job版在线不到1000人女生PhD读不动，出路求建议Java/.Net/JavaScript/NodeJS developer可以写成Software Developer吗快要28岁的生物大龄女生值得转码吗现在大部分的公司找人都说有没有熟悉Azure的同学给结个惑呢？板上的街霸哥们会把活留到第二天吗还互动吗？我14年高喊刷题时没几个信 没几个人懂跟着老板一起跳槽 (转载)想当年我八神的无限鬼步+屑风 还是赢得了众多小伙伴心目中的地位。Ali两年的cliff是不是有点儿黑LC从CF POJ上搬了多少题？请教一个ES问题。多谢！如何解决big data follow up非常好的面经
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。