c******5
发帖数: 84 | 1 一个美国小伙给电面的，问了点数据库的知识，解释下什么是Normalization。
编程题是merge k个长度均为n的sorted的数组，觉得写得不是特别好，后来上网查了下
，比较好
的方法好像有两种，一种是用一个min-heap，还有一种是分成k/2个组，两两归并，然
后再把结果两两归并，直到得到最终结果，时间复杂度应该是O(knlog(k))不过还是给
过了。二面约在了下周一，求bless~~ |
h****n
发帖数: 1093 | |
c******5
发帖数: 84 | 3 数组的sorted的，对时间和内存没有要求。
【在 h****n 的大作中提到】
: 数组是sort的吗，另外对时间和内存有要求么？
|
c******5
发帖数: 84 | 4 一个美国小伙给电面的，问了点数据库的知识，解释下什么是Normalization。
编程题是merge k个长度均为n的sorted的数组，觉得写得不是特别好，后来上网查了下
，比较好
的方法好像有两种，一种是用一个min-heap，还有一种是分成k/2个组，两两归并，然
后再把结果两两归并，直到得到最终结果，时间复杂度应该是O(knlog(k))不过还是给
过了。二面约在了下周一，求bless~~ |
h****n
发帖数: 1093 | |
c******5
发帖数: 84 | 6 数组的sorted的，对时间和内存没有要求。
【在 h****n 的大作中提到】
: 数组是sort的吗，另外对时间和内存有要求么？
|
j******2
发帖数: 362 | 7 我怎么觉得这个两两归并有点荒谬，k个数列还不是要比k-1次，哪会省？
【在 c******5 的大作中提到】
: 一个美国小伙给电面的，问了点数据库的知识，解释下什么是Normalization。
: 编程题是merge k个长度均为n的sorted的数组，觉得写得不是特别好，后来上网查了下
: ，比较好
: 的方法好像有两种，一种是用一个min-heap，还有一种是分成k/2个组，两两归并，然
: 后再把结果两两归并，直到得到最终结果，时间复杂度应该是O(knlog(k))不过还是给
: 过了。二面约在了下周一，求bless~~
|
r**h
发帖数: 1288 | 8 两两归并的思路更方便使用多线程吧？
【在 j******2 的大作中提到】
: 我怎么觉得这个两两归并有点荒谬，k个数列还不是要比k-1次，哪会省？
|
e***s
发帖数: 799 | |
j********g
发帖数: 31 | |
|
|
c********t
发帖数: 5706 | 11 比较lg(k)次，和用heap一样的时间复杂度O(nklog(k))
天晴说的多线程有道理
【在 j******2 的大作中提到】
: 我怎么觉得这个两两归并有点荒谬，k个数列还不是要比k-1次，哪会省？
|
z*******o
发帖数: 4773 | 12 tmobile ?
【在 j********g 的大作中提到】
: 请问LZ T家是指哪家？Bless~
|
n*******w
发帖数: 687 | 13 如果两两归并
比较总次数是 k*n*lg（k）（每层都是kn次比较，lgk层）
一次接一个的归并
比较总次数是 2n + 3n +... + kn = O(k^2*n) > k*n*lg（k）
当k很大的时候lgk比k小得多
【在 j******2 的大作中提到】
: 我怎么觉得这个两两归并有点荒谬，k个数列还不是要比k-1次，哪会省？
|
s*******n
发帖数: 97 | 14 两两归并还是 O(k*n*ｋ)，lgk 层没错，但是每层从 n, 2n, 4n...递增..所以比较次
数没有减少，两两归并用recursive代码比较好写，但是空间复杂度就不好说了
【在 n*******w 的大作中提到】
: 如果两两归并
: 比较总次数是 k*n*lg（k）（每层都是kn次比较，lgk层）
: 一次接一个的归并
: 比较总次数是 2n + 3n +... + kn = O(k^2*n) > k*n*lg（k）
: 当k很大的时候lgk比k小得多
|
s***5
发帖数: 2136 | |
n*******w
发帖数: 687 | 16 你这样的话归并排序变成k^2了，应该不是。n=1退化成基本的归并排序。
具体的计算式应该是
sum {(2^i*n) * (k/2^i)}
i=[1, lgk]
【在 s*******n 的大作中提到】
: 两两归并还是 O(k*n*ｋ)，lgk 层没错，但是每层从 n, 2n, 4n...递增..所以比较次
: 数没有减少，两两归并用recursive代码比较好写，但是空间复杂度就不好说了
|
t*********h
发帖数: 941 | 17 你这个2^i不就抵消了吗 和上面的什么区别？ 貌似结果和heap是一样的
【在 n*******w 的大作中提到】
: 你这样的话归并排序变成k^2了，应该不是。n=1退化成基本的归并排序。
: 具体的计算式应该是
: sum {(2^i*n) * (k/2^i)}
: i=[1, lgk]
|
j******2
发帖数: 362 | 18 编程题就是基本算术，没啥别的
【在 s***5 的大作中提到】
: 这道题可以看出，很多人的基本算术都不行。
|
n*******w
发帖数: 687 | 19 对的。是和sumperman 解释为什么是nklgk
【在 t*********h 的大作中提到】
: 你这个2^i不就抵消了吗 和上面的什么区别？ 貌似结果和heap是一样的
|
