我正在做家庭作業，並且作爲一個「提示」，我們被告知要找到以下算法，然後將其證明爲必要的答案。設L（1），L（2），...，L（k）爲n個元素的排序列表。給出一個支持O（log n + t）Locate操作的O（kn logk）空間算法，該操作返回t個項目的位置。你能幫我弄清楚這個算法嗎？
理想情況下，我將能夠使用這個算法給我一些洞察，以獲得更好的解決方案（這是任務需要的），但這個效率較低的算法應該激勵我，但我無法確定出來。任何想法或知道這個算法是什麼？謝謝！
您是否搜索了O（kn logk）？這似乎是一個非常獨特的大O簽名。
這是我的第一個結果： 歸併 - >What is the relation between merges and number of items in a in k-way merge
我看到一個直接的問題：MergeSort是O（k n log n）* time *算法。問題是*空間*複雜性，而不是時間。 – paxdiablo 2009-04-21 01:30:09
呃...聽起來像...二進制搜索？ Wiki
大概沒有排序功能，因爲你已經有2個排序的列表。聽起來像二進制搜索給我一樣。
我似乎無法找到一個使O（日誌N + T）的時間，但我有一個想法，可能會或可能不會幫助...
O（KN登錄k）是大小的表格將每個可能的項目映射到包含它的列表的編號。然而，使用它來找到哪個列表看起來仍然在* O（log n） - 查找時間爲t元素，所以它不是真的被要求...
我想它會要求你找到首先是低效的算法，然後用它來創建一個高效的算法。這聽起來像是一個列表的線性搜索，每個都有一個二進制搜索來查看它們。這將需要O（2t）空間，因爲您需要複製t個項目的「座標」。
即使有這個醜陋的大O符號，我認爲這是一個二進制搜索問題，因爲你有排序的列表。
空間複雜性保持不變，因爲它是一個分而治之的算法，所以你不會在那裏遇到問題。
要非常確定logn之外的t，例如O（（logn）+ t）？
而n表示項目或元素的數量？ – Cristina 2009-04-22 18:03:49
作業給你，讓你從中學習。如果你在這裏問，你不從中吸取教訓，你只會學習如何提出問題。相信我，試着找出自己並給出錯誤的答案，可能比在這裏問問題並給出正確的答案（由別人給予你的答案）更好，因爲那時你什麼都不學。 – 2009-04-21 07:54:56