PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] Google Interview Question (4)

看板Prob_Solve (計算數學 Problem Solving)作者DJWS (...)時間11年前 (2013/03/15 07:44)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串13/13 (看更多)

※ 引述《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)