2

（たとえば）3つのサブアルゴリズムで構成されるアルゴリズムがある場合、すべて異なるO（）特性を持ちます。例：

  • アルゴリズムA：O（n）
  • アルゴリズムB：O（log（n））
  • アルゴリズムC：O（n log（n））

アルゴリズム全体のO（）を理論的に推定するにはどうすればよいですか？つまり、それを計時したり、他の実際的な測定を実行したりしません。

よく知られている式や手順はありますか？

4

4 に答える 4

9

よく知られている式や手順はありますか？

それが基本的な数学なので、そうです。しかし、あなたの場合はさらに簡単です。これらはすべて上限を与えるので、すべての境界の最大値を取得して、合計の上限を取得できます。

–これらのアルゴリズムがすべて（ネストされているのではなく）連鎖している場合。アルゴリズムがネストされている場合は、それらの上限を乗算する必要があります（最も単純な場合）。

説明のために、単一の要素のルックアップにO（log n ）のコストがかかるコンテナデータ構造があるとします。このようなルックアップを必要とするアルゴリズムもありますが、ルックアップのコストが一定であると想定し、ループごとに一定数のルックアップを使用して入力に対して単一のループを使用すると、実行時間O（ n）自体があります。

ここで、前述のコンテナデータ構造をこのアルゴリズムで使用する場合は、そのルックアップランタイムが（想定される）定数時間ルックアップに明らかに置き換わります。したがって、同じループがありますが、各反復は定数時間O（1）ではなくO（log n）を取るため、全体の実行時間はO（n log n）になります。

于 2009-11-14T11:54:18.230 に答える
4

「全体的な」複雑さは、すべてのサブアルゴリズムの最悪のケースです。あなたの例では：O(n*log(n))

の定義はO(f(n))、ある数（いくつかのn0）から始まり、定数'Const'があり、サイズnの入力に対するアクションの総数が。未満であるということConst*f(n)です。

したがって、サブアルゴリズムのグループがある場合、複雑さは常にすべての定数のシグマ（Const1 + Const2 + ...）に最悪の複雑さの関数（たとえば、 "n"、 "n * logn"、および「n^2」はn^2になります）。複雑さの定義によると、これはグループ内で最悪の複雑さです。

例：

  1. 配列をソートしていると仮定しましょう(n*logn)
  2. キーがxより高いアイテムを検索する (logn)

ソートのConst1が5（5 * n * lognアクション未満でn個のアイテムのリストをソートできることを意味します）であり、Const2が3（3 * lognアクション未満で要素を見つけることができることを意味します）であると仮定します。

この場合、両方のアルゴリズムのアクションの総数がアクションよりも少ないことは明らかで(5+3)*n*lognあり、したがって、O(n*logn)

于 2009-11-14T11:53:49.300 に答える
0

問題の複雑さは、「n」が無限大に向かう条件によって決まります。このリンクは、基本的に、複雑さの少ないすべての O(n) 数が削除される理由です。O(n) 形式でさえ、異なるハードウェアで変化する他の多項式項を削除します。合理的に、関数の時間があれば、さまざまな合計時間を追加できます。これは、呼び出された関数が複数回呼び出される大規模なデータ セットの処理など、時間に依存する環境では意味のあるデータになる可能性があります。これにより、ソリューションのスケーラビリティと、たとえばサーバーでのアップグレードのパフォーマンス ピークが得られる可能性もあります。これは 1 台のマシンのソリューションであり、係数も削除されません。

すべてのマシンは、アーキテクチャとコンパイラがバイナリコードを生成する方法に基づいて、機能を実行する際にさまざまな実行係数を持っています。これは、複数のユーザー向けにプログラムを設計していて、それらが異なるコンピューター上にある場合、特定の計算は無関係であるだけでなく、不正確でもあることを意味します。

計算が無関係でも不正確でもない場合:

別々の構造の秘訣は、1 つの時間関数が他のすべての時間関数ではないということです。

O(n) = x + y + z, 
x(n) = (t1) * (n^2)
y(n) = (t2) * (log n) 
z(n) = (t3) * (n log n)

...

時間 (t1)、(t2)、および (t3) は、特定のマシンでの関数の時間として与えられます。

于 2014-11-26T03:49:51.697 に答える
0

O(n) アルゴリズムの効率推定に関する仮定の 1 つは、実際の実行時間が理論値に近づくということです。したがって、小さな差異を把握しようとして、車軸にあまりこだわるべきではありません。たとえば、ソートされていないデータセットに対して単純な反復検索を行っている場合、O(n) アルゴリズムは O(n/2) 時間で終了する可能性があります (平均して中間点までに値が見つかります)。 O(n) アルゴリズム。

終了する前にデータセットで 3 つのサブプロセスを完了する必要がある関数がある場合、そのデータセットで最も遅いサブプロセスの実行時間は、いわばテント内で最も長い極になります。与えられた特定の例では、関数 ('algorithm') は O(n) 時間で実行され、それが O(n + n*log(n) + log(n)); であるかどうかは心配しません。その合計と O(n) の差は、せいぜい 2 倍です。私たちが気にかけているのは相対的な大きさです。つまり、実行時間が log(n) か (n) か (n^2) か (n^3) 無限であるかということです。私たちが気にするのは、10、100、または 1000 の係数です。

于 2009-11-30T09:08:32.827 に答える