f****4
发帖数: 1359 | 1 如果用heap实现的话，这个时间复杂度怎么算？
O(n)? 还是O(n+n*logk)->O(n*logk)？
之前算时间复杂度，都是把程序各个部分需要run多少步加起来然后算big O
但是又看到说树遍历的是O(n)说是stack操作，不用计算时间复杂度，那如果是那样的
话，k个最大数就是O(n)
谁能解释一下，到底是那种算法？
谢谢 |
m*****g
发帖数: 226 | |
f****4
发帖数: 1359 | 3 那最差的情况，为啥是nlogn？
能详细解释一下么？ 还有，这个是O(nlogn)还是，就是nlogn?
【在 m*****g 的大作中提到】
: 用heap, 最佳 n, 最差 nlogn
|
k***e
发帖数: 556 | 4 linear selection
【在 f****4 的大作中提到】
: 如果用heap实现的话，这个时间复杂度怎么算？
: O(n)? 还是O(n+n*logk)->O(n*logk)？
: 之前算时间复杂度，都是把程序各个部分需要run多少步加起来然后算big O
: 但是又看到说树遍历的是O(n)说是stack操作，不用计算时间复杂度，那如果是那样的
: 话，k个最大数就是O(n)
: 谁能解释一下，到底是那种算法？
: 谢谢
|
f****4
发帖数: 1359 | 5 我知道我把哪搞混了，我写一下，有错的话，请指出来，谢谢
Time Complexity measures分 Best, worst and average
用具体操作的布数来衡量
Big O 给了一个 Upper and lower bounds on the complexity
所以，如果给问到Time Complexity就的列出在那种衡量方法下的布数之和
例如：k个最大数问题
最优，arr从大到小排序，heap不需要进行调整，前k个就是答案；所以操作步骤是n步
；最坏，arr从小到大排序，heap需要调整，步骤 n + n*logk
用big O的话是O(nlogk) <--这个还是不确定到底对不对
【在 m*****g 的大作中提到】
: 用heap, 最佳 n, 最差 nlogn
|
m*****g
发帖数: 226 | 6 我的理解，big O 是upper bound
theta O 才是上限和下限
所以O(n+nlgn) = O(nlgn)
对。那个应该是nlgk。这个是我不仔细。 |
s********l
发帖数: 998 | 7 我怎么觉得是n*logk呢
因为fix heap要logk 然后又有n个element~~
【在 f****4 的大作中提到】
: 如果用heap实现的话，这个时间复杂度怎么算？
: O(n)? 还是O(n+n*logk)->O(n*logk)？
: 之前算时间复杂度，都是把程序各个部分需要run多少步加起来然后算big O
: 但是又看到说树遍历的是O(n)说是stack操作，不用计算时间复杂度，那如果是那样的
: 话，k个最大数就是O(n)
: 谁能解释一下，到底是那种算法？
: 谢谢
|
D***h
发帖数: 183 | 8 用heap就是O(nlogk)
一般不明确说明的话，都是指最坏情况的。
我知道我把哪搞混了，我写一下，有错的话，请指出来，谢谢
Time Complexity measures分 Best, worst and average
用具体操作的布数来衡量
Big O 给了一个 Upper and lower bounds on the complexity
所以，如果给问到Time Complexity就的列出在那种衡量方法下的布数之和
例如：k个最大数问题
最优，arr从大到小排序，heap不需要进行调整，前k个就是答案；所以操作步骤是n步
；最坏，arr从小到大排序，heap需要调整，步骤 n + n*logk
用big O的话是O(nlogk) <--这个还是不确定到底对不对
【在 f****4 的大作中提到】
: 我知道我把哪搞混了，我写一下，有错的话，请指出来，谢谢
: Time Complexity measures分 Best, worst and average
: 用具体操作的布数来衡量
: Big O 给了一个 Upper and lower bounds on the complexity
: 所以，如果给问到Time Complexity就的列出在那种衡量方法下的布数之和
: 例如：k个最大数问题
: 最优，arr从大到小排序，heap不需要进行调整，前k个就是答案；所以操作步骤是n步
: ；最坏，arr从小到大排序，heap需要调整，步骤 n + n*logk
: 用big O的话是O(nlogk) <--这个还是不确定到底对不对
|
|
v******n
发帖数: 421 | 9 取k个不是klogn ?
【在 D***h 的大作中提到】
: 用heap就是O(nlogk)
: 一般不明确说明的话，都是指最坏情况的。
:
: 我知道我把哪搞混了，我写一下，有错的话，请指出来，谢谢
: Time Complexity measures分 Best, worst and average
: 用具体操作的布数来衡量
: Big O 给了一个 Upper and lower bounds on the complexity
: 所以，如果给问到Time Complexity就的列出在那种衡量方法下的布数之和
: 例如：k个最大数问题
: 最优，arr从大到小排序，heap不需要进行调整，前k个就是答案；所以操作步骤是n步
|
D***h
发帖数: 183 | 10 建大小为k的堆，每次操作是logk, n个元素，所以总共是O(nlogk).
【在 v******n 的大作中提到】
: 取k个不是klogn ?
|
|
|
f****4
发帖数: 1359 | |
s*******n
发帖数: 97 | 12 Yes....That is better....
【在 k***e 的大作中提到】
: linear selection
|
v******n
发帖数: 421 | 13 也可以建大小为 n 的堆，k 次 extract-min, O(n + k log n)
跟 O(k + n log k) 比较，要看 k 的数量级
【在 D***h 的大作中提到】
: 建大小为k的堆，每次操作是logk, n个元素，所以总共是O(nlogk).
|
b********h
发帖数: 119 | 14 建大小为n的堆需要nlog(n)的时间吧。
【在 v******n 的大作中提到】
: 也可以建大小为 n 的堆，k 次 extract-min, O(n + k log n)
: 跟 O(k + n log k) 比较，要看 k 的数量级
|
v******n
发帖数: 421 | |
m******e
发帖数: 64 | |
