re: 面试归来，上面经回馈各位战友 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

re: 面试归来，上面经回馈各位战友

re: 面试归来，上面经回馈各位战友# JobHunting - 待字闺中

k*j2011-08-21 07:08

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*n2011-08-21 07:08

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*j2011-08-21 07:08

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)