問題タブ [time-complexity]

次のコードの時間計算量を計算する必要があります。

O(n^2)ですか？

各ノードが最大で 3 つの子と 3 つの親を持つ *n サイズの多頭非巡回グラフが与えられた場合、2 つのノードが同じ値を共有しない n 長のパスが存在するかどうかを識別する非指数アルゴリズムはありますか?セットの値は説明されますか?

基本的に、各スペースにランダムな値 (1..n) を持つ n*n 迷路があります。すべての値を含む n ノードの (上から下への) パスを見つける必要があります。

現在、深さ優先検索を使用していますがT(n) = 3T(n-1) + O(1)、それはO(3^n)理想的ではない解決策です。

私の恐れを確認するか、正しい方向に向けていただければ幸いです。

編集：これをもう少し具体的にするために、ここに解決策のある迷路があります（深さ優先の解決策を使用して解決されます）。

複雑さ log2(n)/5 のソートされた配列で検索するためのアルゴリズムをコーディングしました。役に立ちますか?

結果のO表記と分析方法の独自性の両方に関して、驚くべき（タフで奇妙な）複雑さ分析を持っていると思うアルゴリズムはどれですか？

Project Eulerやその他のコーディング コンテストでは、多くの場合、実行に最大の時間がかかったり、特定のソリューションの実行速度を自慢したりします。Python では、タイミング コードを .xml ファイルに追加するなど、アプローチがややぎこちない場合があります__main__。

Python プログラムの実行にかかる時間をプロファイリングする良い方法は何ですか?

一般に、複雑な関数を分析する場合、定義する変数は 1 つまたは 2 つだけではないため、"n" を定義するのが難しいのではないかと思います。

循環的複雑度の分析ツールはありますが、時間 (および/または空間) 複雑度の分析ツールはありますか? もしそうなら、それはどれですか？そうでないなら、なぜですか？それは実行不可能ですか？不可能？誰かがそれに慣れていないだけですか？

理想的には、アプリケーションの全体的な複雑さのようなもの (さまざまな可能な "n" を定義する) と、アプリ内の各メソッドのようなものがあるでしょう。

編集：停止問題のために正確な解決策は不可能のようですが、ある種のヒューリスティックな近似は可能ですか? 実用的な目的では、優れたプロファイラーがはるかに有用な情報を提供することを認識していますが、それは興味深い問題のようです。

また、プログラムの特定のサブセットを計算するものはどうですか?

プリムのアルゴリズムのウィキペディアのエントリを見ていましたが、隣接行列を使用した時間の複雑さが O(V^2) であり、ヒープと隣接リストを使用した時間の複雑さが O(E lg(V)) であることに気付きました。ここで、E はV はグラフの頂点の数です。

Prim のアルゴリズムはより密なグラフで使用されるため、E は V^2 に近づくことができますが、近づくと、ヒープの時間計算量は O(V^2 lg(V)) になり、O(V^2) よりも大きくなります。明らかに、ヒープは単に配列を検索するよりもパフォーマンスを向上させますが、時間の複雑さはそうではありません。

改善によってアルゴリズムの速度が実際にどのように低下​​するのでしょうか?

[0..n ^ 3-1]の範囲のn個の整数の入力セットが与えられた場合、線形時間ソートアルゴリズムを提供します。

これは木曜日の私のテストのレビューであり、この問題にどのように取り組むべきかわかりません。

O(n log n)のMergeSortだと思います。

ただし、次の出力は一致しません。

4 つのノードのノードリストをシーケンス番号で並べ替えています。並べ替えは 6 回の比較を行っています。6 > (4 log(4)) なので困惑しています。誰かが私にこれを説明できますか？

PSマージソートですが、まだ結果がわかりません。

回答ありがとうございます。トム、私の数学を訂正してくれてありがとう。

このアルゴリズムの時間の複雑さと、それが O(n^2) である理由を誰でも手伝ってもらえますか。ステップバイステップの説明は役に立ちます、ありがとう！