問題タブ [time-complexity]

プリム法を使用してMSTを解決するコードを作成しました。この種の実装（優先キューを使用）はO（E + VlogV）= O（VlogV）である必要があることを読みました。ここで、Eはエッジの数、Vはエッジの数ですが、コードを見ると単純に見えません。誰かが私のためにこれを片付けることができれば私はそれをいただければ幸いです。

私には、実行時間はこれであるように思われます：

whileループにはO（E）回かかります（すべてのエッジを通過するまで）そのループ内で、O（logE）時間かかるQから要素を抽出します。そして、2番目の内側のループにはO（V）時間がかかります（すべての頂点を追加する必要があるため、このループがV回実行されることは明らかですが、毎回このループを実行するわけではありません）

私の結論は、実行時間は次のとおりです。O（E（logE + V））= O（E * V）。

これは私のコードです：

変更リストを別のシステムにプッシュするシナリオがあります。各リストには、挿入、更新、または削除された通知が 0 個以上含まれています。

挿入は簡単です。通知には、ターゲット インデックスとアイテムへのポインターが含まれます。更新は簡単です。アイテムへのポインターを渡します。

削除は簡単に思えます。削除するアイテムのインデックスを渡す必要がありますが、どうすればインデックスを知ることができますか? インデックスはゼロから始まり、連続している必要がありますが、挿入時に作成します。そのため、各項目に対して作成したインデックスを追跡する必要があります。

たとえば、 map: でこれを行うことができますがstd::map<item*, int>、アイテムを削除すると、それ以降のすべてに番号を付け直す必要があります。これは O(N) です。

これらのアイテムのリストは、O(N) 反復が受け入れられないほど大きくなります。この問題は解決されたと確信していますが、解決策が何と呼ばれるかはわかりません。「リンクされたリスト」に関連するものを検索すると、大量のノイズが発生します。

考えられる解決策の 1 つはスキップ リストです。サブリスト内の各ノードは、スキップするメイン リスト内のノードの数を認識しています。スキップ リストの検索は O(log N) であるため、移動しながら追跡し、インデックスを見つけることができます。 O(log N)、O(log N) 内のアイテムも削除します。

ただし、スキップ リストの実装はやり過ぎのように思えます...もっと簡単な解決策はありますか?

編集：

あなたの提案に感謝しますが、スキップリストがここでこの問題を解決する正しい方法であると確信していると思います.

アルゴリズムの上限または下限を証明するとはどういう意味ですか?

オブジェクトの大規模なコレクションがあり、それらの間の類似点を把握する必要があります。

正確に言うと、2 つのオブジェクトが与えられた場合、それらの非類似度を数値 (メトリック) として計算できます。値が大きいほど類似度が低くなり、0 はオブジェクトの内容が同一であることを意味します。この数値を計算するコストは、小さいオブジェクトのサイズに比例します (各オブジェクトには特定のサイズがあります)。

オブジェクトが与えられた場合、それに類似したオブジェクトのセットをすばやく見つける機能が必要です。

正確に言うと、任意のオブジェクト o を、d よりも o に似ていないオブジェクトのセットにマップするデータ構造を作成する必要があります。配列またはリンクされたリストにありました（そしておそらく実際にそうです）。通常、セットはオブジェクトの総数よりもはるかに小さいため、この計算を実行することは非常に価値があります。データ構造が固定の d を想定していれば十分ですが、任意の d で機能する場合はさらに優れています。

以前にこの問題、またはそれに類似した問題を見たことがありますか? 良い解決策は何ですか？

正確に言うと、単純な解決策には、オブジェクトのすべてのペア間の非類似度を計算することが含まれますが、これは時間がかかります - O(n ² ) ここで、n はオブジェクトの数です。複雑さの低い一般的なソリューションはありますか?

二重リンクリスト（O（1））でのノード削除の時間計算量が、単一リンクリスト（O（n））でのノード削除よりも速いのはなぜですか？

アルゴリズム解析を学んでいます。O、Ω、Θの違いがよくわかりません。

それらの定義方法は次のとおりです。

• f(n) = O(g(n))c · g(n)は の上限を意味しf(n)ます。したがって、常に ≤で あるcような定数が存在します。f(n)c · g(n)nn ≥ n0n0
• f(n) = Ω(g(n))c · g(n)は の下限を意味しf(n)ます。したがって、すべての に対して常に ≥となる定数cが存在します。f(n)c · g(n)n ≥ n0
• f(n) = Θ(g(n))すべてのについて、 はc1 · g(n)の上限でf(n)あり、c2 · g(n)は の下限であることを意味します。 したがって、定数などが存在し、 およびが存在します。これは、 に対して適切でタイトな境界を提供することを意味します。f(n)n ≥ n0c1c2f(n) ≤ c1 ·g(n)f(n) ≥ c2 ·g(n)g(n)f(n)

私がこれを理解した方法は次のとおりです。

• O(f(n))指定された関数/アルゴリズムの最悪の場合の複雑さを示します。
• Ω(f(n))与えられた関数/アルゴリズムの最良のケースの複雑さを示します。
• Θ(f(n))与えられた関数/アルゴリズムの平均的なケースの複雑さを示します。

間違っている場合は修正してください。その場合、各アルゴリズムの時間計算量は、3 つの表記法すべてで表現する必要があります。しかし、O、Ω、または Θ のいずれかで表されることがわかりました。なぜ3つすべてではないのですか？

ゲーム Globs ( http://www.deadwhale.com/play.php?game=131 ) を解決するためのアルゴリズムとデータ構造を提案してください。オタクな意味でとても楽しいです。

アプローチの時空間の複雑さ (big-O) をグリッドのサイズ (N>=14) で表します。複雑さが低く、十分に効率的なアルゴリズムが優先されます。

(MatrixFrog は、このゲームが FloodIt としても知られていることを正しく指摘しており、Smashery は 3 か月前に、彼が以下に引用したリンクで解決策を示しました。あなたたち全員が、最適ではない解決策を提供する 1 回の先読みのみでプルーニング/貪欲を提案しています。)

ゲームは nxn ノードのランダムな正方形グリッドを生成します。各ノードは 6 色 (Grn=1、Ylw=2、Red=3、Blu=4、Pur=5、Orn=6) のいずれかに着色されています。レベル 1 には 9x9 のグリッドがあり、n は各レベルを最大 14 まで増やします。各レベルは最大 25 ターンを取ることができます。各ターンで、左上のノードを変更する色を選択します。たとえば、新しい色の接続された隣接する (水平/垂直) ノードが形状に同化され、同化されたノードごとに 1 ポイントが追加されます。あなたのスコア。スコアリングの目的は、各グリッドをできるだけ少ないターンで完了することです。たとえば、16 ターンで完了した場合、未使用の 9 つの移動 => 累積スコアの 2*9 乗数倍になります。

明らかに、これを分解する方法はたくさんあります。14x14 グリッドを使用した再帰的バックトラッキングのデフォルトの選択は実行可能な候補です。これは、他にどのようなタイプのデータ構造に適していますか? あ*? 最適性にこだわらないでください。「十分な」アルゴリズムがあるかどうか疑問に思っています。

(ロボットのコードを作成して馬鹿げた高得点を獲得するのは楽しいプロジェクトかもしれないと思いました。ただし、3.5E+12 はすべてフレッシュウェアの自分で採点しました。)

4n ^ 2 + 7nの移動で達成するアルゴリズムがある場合、そのOは何ですか？O（4n ^ 2）？O（n ^ 2）？

7nがカットオフされていることは知っていますが、n^2係数を維持する必要があるかどうかはわかりません。

ありがとう

セットアップ (MySQL):

これは私の以前の投稿の BFS ソリューションです。

チャレンジ、6次分離のアルゴリズムを実装する方法は?

しかし、それの複雑さは何ですか?完全にnレコードがあるとします。