作者DJWS (...)
看板Prob_Solve
标题Re: [问题] Google Interview Question (4)
时间Fri Mar 15 07:44:02 2013
※ 引述《stimim (qqaa)》之铭言：
: 於是，我们就可以得到一个小一点的问题，
: lists = {list_1, list_2, ..., list_K}
: where list_1 = {p_1j},
: list_i = {a_i, b_i}
: 这个问题的大小是 O(K) ，如果可以在 O(K) 的时间得到答案的话，
: 我们就可以用 O(N) 的时间得到原问题的答案：
以下尝试说明这个小一点的问题
目标是每个list_i当中，ai和bi两个选一个，
让 max{abs(ai)} + max{bi} 越小越好。
http://postimage.org/image/xfpn6lbe3/
首先把 [ai,bi] 画在数线上，按照 ai 由小到大排序
http://postimage.org/image/t4icz76cx/
如果已经排序好，
就可以 ai 由小到大扫描一次所有区间，O(K) 算出答案。
我们要找的答案，是最短的红线。
(这个好难解释，总之各位应该看得懂吧...一开始假设通通都选ai这样...)
http://postimage.org/image/5c91no4c1/
可以发现这些区间可以分成一堆一堆的盘子，
就好像叠盘子一样，每一堆最下面的是大盘子，上面有一些小盘子。
所有的小盘子的边缘，都不会超过最下面的大盘子。
如果还没有排序好，
这个问题比找出所有的 dominating intervals 还要难一点。
dominating intevals 就是每一堆盘子里面，最下面的大盘子。
define [ai,bi] dominates [aj,bj] iff ai<=aj and bi>=bj
dominatring intervals 又可以等价变成二维平面上的 dominating points。
(CLRS 叫做 maximal layer)
只要把区间 [ai,bi] 改成二维座标 (-ai, bi) 即可。
也就是说这个问题至少比 maximal layer 来的复杂。
至於 maximal layer 的严格下限是 omega(NlogM)，
其中 N 是给定的座标数量，M 是 maximal layer 的数量，证明在这篇：
Lower bounds for maximal and convex layers problems
Algorithmica, June 1989, Volume 4, Issue 1-4, pp 447-459
不是很懂那个 algebraic dicision tree model 是指什麽意思，
不过我的理解是：除非用 counting sort 之类的技巧，不然这题应该很难做到 O(K) 吧!
报告完毕
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
补充一下原题的 worst case lower bound。
stimim 的方法是：
在 K 个 inverted list 当中，找到长度最短的那个 inverted list，
然後穷举长度最短的 inverted list 当中的每一个 occurrence，
针对每个 occurrence，从其他 inverted list 找到 [ai,bi]，
进而得到一个小一点的问题。
运气不好时，最短的 inverted list 长度是 omega(N/K)。
【这里的 N 是指全部的、也就是那K个 inverted list 的总长度。】
所以穷举的次数就是 omega(N/K)。
运气不好时，每个小问题之间的 [ai,bi] 通通都不一样。
所以每个小问题之间没有关联，可以分开计算。
解决一个小问题的下限，如前文所述，就是 omega(KlogK)。
所以原本问题的下限就是 omega(N/K * KlogK) = omega(NlogK)。
所以这一题不会有 O(N) 的方法。
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 36.225.132.202
※ 编辑: DJWS 来自: 36.225.132.202 (03/15 10:25)