6

私の数学の背景はあまり良くありません.

  1. n^2/3 で。n^2/3 = 立方根 n * 立方根 n なので、

    public void test(int n){
    for (int i = 0; i*i*i < n; i++) {
        for (int j = 0; j*j*j < n; j++) {
            count ++;
        }
    }
}

  2. 4^n で。フィボナッチ法は使えますか？

    public int fibonnaci(int n) {
    if (n <= 1) {
        return 1;
    } else {
        return fibonnaci(n - 2) + fibonnaci(n - 1);
    }
}

上記のコードが正しいかどうかわかりますか? どうもありがとう！

4

3 に答える 3

5

最初のものは正しく、本当によく考えられています。

二つ目はそうではありません。fibs を計算するアルゴリズムは、O(n^4) よりも時間の複雑さがはるかに高くなります (編集:この回答を書いたときに尋ねられたものでした - 質問はその間に更新されました)。多項式でさえありません。理由は次のとおりです (表記 #fib(x): fib(x) を計算するために fib が呼び出される回数):

  • fib(1): #fib(1) = 1 (結果を直接返す)
  • fib(2): #fib(2) = 3 (fib(2) 用に 1 つ、fib(0) および fib(1) 用に呼び出す)
  • fib(3): #fib(3) = 5 (fib(3) に 1 つ、fib(2) と fib(1) にそれを呼び出し、さらに 3 + 1 回呼び出します)
  • fib(4): #fib(4) = 9
  • fib(5): #fib(5) = 15
  • fib(6): #fib(6) = 25
  • ...
  • fib(i): #fib(i) = 1 + #fib(i-1) + #fib(i-2)

だから、あなたは持っています：

  • #fib(i) ~= #fib(i-1) + #fib(i-2)

このことから、fib(i) の計算には、fib(i-1) の計算にかかる時間の「約」(実際には、それよりも少し少ない) 2 倍の時間がかかると合理的に推測できます。したがって、O(#fib(i)) = O(2^i) と「推測」できます。これは帰納法で簡単に証明できる正解です。

フィボナッチ数列について最後に、n 番目の数を計算するためのはるかに高速なアルゴリズムがあります。たとえば、線形時間 (つまり、O(n)) を使用するアルゴリズムは、作成した関数をメモ化します (つまり、Map を参照して、n の結果がわかっているかどうかを確認し、すぐに返し、そうでない場合は計算します)。保管して返却してください）。n 番目の fib を計算するための閉じた式もあるため、一定時間アルゴリズム (つまり、O(1)) です。

最後に、O(n^4)アルゴリズムの例は、4 つの内部ループを持ち、各ループが「約」n 回実行されるものです。

たとえば、面 n の n 個の立方体の体積を (最適ではない方法で) 計算します。

int volume = 0;
for (int cube = 0; cube < n; cube++)
  for (int x = 0; x < n; x++)
    for (int y = 0; y < n; y++)
      for (int z = 0; z < n; z++)
        volume++;
return volume;
于 2012-10-14T06:10:12.577 に答える
1

これは本当の答えではありませんが、時間がかかるプログラムの例を提供するという問題に対する「チート」ソリューションのスケッチを次に示しO(F(N))ます。

  1. F(N)指定されたを評価する Java 関数オブジェクトを作成しますN。

  2. それをパラメーターとして次のメソッドに渡します。

   public void computeOrderFN(int n, FunctionInt2Int fn) {
      int count = fn.evaluate(n);
      for (int i = 1; i < count; i++) {
          // Do something O(1) that the compiler can't optimize away)
      }
   }

ただし、「賢い**」であるという信用を失うリスクがある場合は、これを使用しないでください:-)

于 2012-10-14T06:31:51.310 に答える
1

その大きな制限の時間の複雑さを要するコードを書いているだけですか?

＃1よりも、はい、かかりO(n^(2/3))ます。

しかし、#2 の場合、コードは 、 、および 1.6.. を取りO(2^n)、theta(1.6...^n)有名な黄金比の数です。

参考：フィボナッチ数列の計算量

于 2012-10-14T06:01:47.540 に答える