0

私はCLRSの第3章に取り組んでいます。これは実行時間に関するものであり、いくつかの例を実行したいと思います。私はアルゴリズムクラスに登録していないので、wwwに助けを求める必要があります。

1）n ^ 2 =ビッグオメガ（n ^ 3）

このステートメントは誤りだと思います。最良の実行時間がn^3の場合、アルゴリズムをn^2にすることはできません。最良の場合でさえ、それよりも遅いです。

2）n + log n =ビッグシータ（n）

このステートメントは正しいと思います。lognの下位項は無視できます。これにより、最悪の場合の実行時間はBig-Oh（n）になります。そして、Big-Omega（n）の実行時間のベストケース。しかし、これについてはよくわかりません。もう少し説明していただければ幸いです。

3）n ^ 2 log n = Big-Oh（n ^ 2）

this.statementは誤りだと思います。最悪の場合の実行時間はn^2lognである必要があります。

4）n log n = Big-Oh（n sqrt（n））

n log n <n sqrt（n）であるため、真である可能性があります。しかし、よくわかりません。

5）n ^ 2-3n-18 =ビッグシータ（n ^ 2）本当にわからない...

6）f（n）= O（g（n））およびg（n）= O（h（n））の場合、f（n）= O（h（n））。

推移的なプロパティによって保持されます。

誰かが私のかなり間違った答えについて少し詳しく説明してくれることを願っています:)

4

1 に答える 1

4

  1. あなたは正しいですが、理由はそうではありません。Omega（n ^ 3）はアルゴリズムに直接関係するのではなく、関数に関係することを忘れないでください。
    あなたが正しい理由は次のとおりです。定数ごとc,Nに、次のn>Nようなものがありますn^2 < c * n^3—したがって、n^2Omega(n^3)

  2. あなたは正しいです。 （十分にn < n + logn < 2*n大きいnの場合）、したがってn + logn、O(n)Omega(n)

  3. あなたは正しいですが、ここでも「最悪の場合」を使用しないでください。説明と証明のガイドラインは1と同様になります。

  4. log(n)は漸近的により小さくsqrt(n)、残りはそれに続くので、これは正しいです。

  5. 1と同じ原理。同じアプローチでも当てはまります。

  6. 正しい。

補足として：Omega(n)「のベストケース実行時間n」を意味するのではなく、複雑さ（ワーストケースの複雑さ、ベストケースの複雑さ、または平均的なケースの複雑さなど）を示す関数Omega(n)がであるための条件を保持することを意味します。

例-クイックソート：

  • 最悪の場合の分析では、Theta(n^2)
  • 一方、平均的なケース分析では、Theta(nlogn)
于 2012-11-25T13:16:48.607 に答える