1

私はこれらの2つの質問に答える方法を理解していると思います(質問の後の答え)。時間計算量の計算とBigOの見つけ方を理解しているかどうかを確認したかっただけです。
一般的な形式は、式の右側にある各値の積にすぎません。
BigOは、多項式で最大のパワーです。この考え方は正しいですか?

int sum = 0;
for (int i = 0; i < n; i++)
   for (int j = 0; j < n * n; j++)
      for (int k = 0; k < 10; k++)
         sum += i;

このコードには、一般的な時間単位がいくつかかりますか?n(n ^ 2)* 10このコードの実行時間はどれくらいですか?O(n ^ 3)

4

2 に答える 2

1

はい。基本的に、大きなOの定義は、時間単位(あなたがそれらと呼ぶ)は、ある(任意に高い)自然数から無限大までの定数時間によって上から制限されることを示しています。より数学的な表記法では、これは次のとおりです。

関数f(n)は、定数Cと、すべてのn> Nに対してf(n)<C * g(n)となる数Nが存在する場合、O(g(n))です。

あなたの文脈では、f(n)= n(n ^ 2)* 10およびg(n)= n^3です。

ちなみに、関数はO(n ^ 4)と言うこともできます。ビッグシータ表記を使用して、これが下限でもあることを示すことができます。f(n)は$ \ theta(n ^ 3)です。

詳細については、https://en.wikipedia.org/wiki/Big_O_notationをご覧ください。

于 2012-04-30T05:54:44.920 に答える
1

はい、あなたの理解は正しいです。ただし、対数項も処理する必要がある場合があります。対数項を見る方法は、n ^(1 +イプシロン)として見ることです。イプシロンは少量です。

于 2012-04-30T05:47:36.987 に答える