1

O(m) 時間で実行されるアルゴリズムがあります。このアルゴリズムは、m 個のエントリを含む一連のデータを取り込みます。

データは、厳密に正の整数入力 n を指定することによってランダムに生成されます。生成されるエントリの数は O(n log n) です。

編集

単独で、データを生成する時間の複雑さは n (または O(1)) とは無関係です。つまり、整数 n が与えられると、エントリは即座にランダムに生成されます。結果のエントリの数はランダムですが、O(n log n) です。たとえば、n = 10 の場合、生成されるエントリの数は 10 の定数倍 (log 10) になります。

データは事前​​に生成されます。次に、結果の m エントリが入力としてアルゴリズムに供給されます。

質問

次に、アルゴリズムが O(n log n) 時間で実行されると想定できますか?

4

1 に答える 1

2

あなたの質問には、入力サイズと実行時の複雑さの関係を理解するのに役立つように意図的に配置されているか、誤解によって引き起こされた単純な曖昧さがいくつかあります。

したがって、このシナリオを解釈できる限り：

アルゴリズムの複雑さは、 m に関してO(m)線形です。

したがって、時間の複雑さは、エントリを生成するように指定しWe assume that generating the data is independent of input. i.e. O(1).たものにのみ依存します。n

そうですO(n log n)、 size の入力に対して何もしないので、アルゴリズムは時間内に実行されると言えますm。

更新された質問への回答:

いくつかのキーワードは異なるものを指しているため、理解するのはまだ難しい. しかし、一般的に、これはあなたが得ているものだと思います：

  • 特定のnが与えられた場合、入力としてデータセット、つまりサイズO（n log n）があります。
  • このデータセットは入力としてのみ使用されます。事前に生成されるか、ブラックボックスに与えられた n に関係なく O(1) 時間で実行されるブラックボックスを使用して生成されます。(この質問のブラックボックスには興味がありません)
  • このデータセットは、実際に分析したいアルゴリズムに送られます。
  • このアルゴリズムは、サイズ m の入力に対して時間複雑度 O(m) を持ちます。
  • 入力のサイズは n に関して O(n log n) であるため、拡張により、O(m) 線形時間アルゴリズムは n に関して O(n log n) の時間複雑度を持ちます。

違いを確認するには: アルゴリズムが線形ではなく二次 O(m^2) であると仮定すると、n に関して時間複雑度 O(n^2 log^2 n) になります。

于 2012-12-03T18:26:31.440 に答える