k*j 发帖数: 153 | 1 翻出了这个老题,大家来讨论一下。下面是我的答案,不知道对不对,望指点。
http://www.mitbbs.com/article_t1/JobHunting/31848109_0_1.html
1. 两个sorted array, 如果merge成一个array。
O(m+n)
2. 如果这两个array没有sort呢?并分析复杂度。
O(nlgn)+O(n) if(m>n)
3. 如果有K个没有sorted的array怎么办呢?
kO(nlgn)+kO(n)
4. 如果当前机器有K个cpu, 怎么处理问题3呢?复杂度分析。
O(nlgn)+kO(n) | k****n 发帖数: 369 | 2
wrong, can unsorted array merging faster than sorted ones?
I see, I guess you mean kO(nlgn)+kO(n), but actually should be kO(nlgn)+kn(
lgk)
sort k arrays individually, O(nlgn)
divide & conquer, 2n 1st level, 4n 2nd level, ... kn at root,
lgk levels in total O(kn)
【在 k*j 的大作中提到】 : 翻出了这个老题,大家来讨论一下。下面是我的答案,不知道对不对,望指点。 : http://www.mitbbs.com/article_t1/JobHunting/31848109_0_1.html : 1. 两个sorted array, 如果merge成一个array。 : O(m+n) : 2. 如果这两个array没有sort呢?并分析复杂度。 : O(nlgn)+O(n) if(m>n) : 3. 如果有K个没有sorted的array怎么办呢? : kO(nlgn)+kO(n) : 4. 如果当前机器有K个cpu, 怎么处理问题3呢?复杂度分析。 : O(nlgn)+kO(n)
| k*j 发帖数: 153 | 3 对。不好意思,我那是笔误,O(nlgn)都错写成了O(lgn)
谢谢。我才意识到merge k个array需要一个heap(size k)来找当前最小值,所以每一步都需要lg(k)时间。总共是nk个元
素,nkO(lgk)
【在 k****n 的大作中提到】 : : wrong, can unsorted array merging faster than sorted ones? : I see, I guess you mean kO(nlgn)+kO(n), but actually should be kO(nlgn)+kn( : lgk) : sort k arrays individually, O(nlgn) : divide & conquer, 2n 1st level, 4n 2nd level, ... kn at root, : lgk levels in total O(kn)
| y******n 发帖数: 47 | 4
这是怎么来的? 能解释以下么?
【在 k*j 的大作中提到】 : 对。不好意思,我那是笔误,O(nlgn)都错写成了O(lgn) : 谢谢。我才意识到merge k个array需要一个heap(size k)来找当前最小值,所以每一步都需要lg(k)时间。总共是nk个元 : 素,nkO(lgk)
| m****t 发帖数: 555 | 5
这个感觉不对。设想m=1000000, n=10, 则复杂度绝对不会是O(nlgn)+O(n)
【在 k*j 的大作中提到】 : 对。不好意思,我那是笔误,O(nlgn)都错写成了O(lgn) : 谢谢。我才意识到merge k个array需要一个heap(size k)来找当前最小值,所以每一步都需要lg(k)时间。总共是nk个元 : 素,nkO(lgk)
|
|