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)
|
|
