私は宿題に取り組んでいます。「ヒント」として、以下のアルゴリズムを見つけて、それを必要な答えに証明するように指示されています。このアルゴリズムを理解する手助けはできますか？
L（1）、L（2）、...、L（k）をそれぞれn個の要素のソートされたリストとする。 t個の項目の位置を返すO（log n + t）Locate操作をサポートするO（kn logk）空間アルゴリズムを与えます。
理想的には、このアルゴリズムを使用して、より良い解決策（課題が望むもの）を達成するためのいくつかの洞察を得ることができますが、この効果の低いアルゴリズムは私にインスピレーションを与えるはずですが、それを出す。どんな考えか、このアルゴリズムが何であるか知っていますか？ありがとう！
あなたはO（kn logk）でグーグルしましたか？それはかなり独特のビッグ・オウン・シグニチャであるようです。すでに2つのソートリストを持っているので、おそらく>What is the relation between merges and number of items in a in k-way merge
私が見ている直面する問題の1つ：MergeSortはO（k n log n）* time *アルゴリズムです。問題は時間ではなく、*空間*の複雑さであった。 – paxdiablo
ehh ...のように聞こえる...バイナリ検索？ Wiki
ないソート機能 - マージ：ここ
は私の最初の結果です。バイナリサーチのように聞こえます。
私はOを与える1（ログのn + t）は時間を見つけるように見えることはできませんが、私はか...
O（KN kはログ）サイズで助けないかもしれないかもしれないと思っていました可能な各アイテムをそれを含むリストの番号にマッピングするテーブルを作成します。しかし、それを使って調べるリストを見つけても、* O（log n） - t要素の見積もり時間になるので、実際に何が求められているかは分かりません...
私はあなたにまず効率の悪いアルゴリズムを作成し、それを使って効率的なアルゴリズムを作成します。リストの線形検索のように聞こえ、それぞれがバイナリ検索で検索できます。あなたはt個のアイテムの "座標"をコピーする必要があるので、O（2t）スペースが必要です。
醜い大きなO表記でも、ソートされたリストがあるので、バイナリ検索の問題だと思います。
空間の複雑さは分裂と征服のアルゴリズムであるので、問題はありません。
O（（logn）+ t）のようなlognの外側のtは本当に確実でしょうか？
そして、nはアイテムまたは要素の数を表しますか？ – Cristina
宿題はあなたに与えられ、あなたはそれから学びます。あなたがここで尋ねるならば、あなたはそれから学ぶことはできません、あなたは質問をする方法を学ぶだけです。私を信じて、あなたが何かを覚えていないので、おそらくあなた自身を見つけて間違った答えを出すのが、ここで聞いて正しい答えを与えるよりも良いでしょう。 –