0

これが私の機能です。それは単純なものです、私は答えが何であるかについて自信がありません。

  int calcul( int n) {
    if(n=1)
      return 1;
    else
      return calcul(n/2) + 1;
  }

さて、複雑さを得るために、私は次のことを行います。

T（n）= T（n / 2）+ O（1）

T（n / 2）= T（n / 4）+ O（1）

..。

T（1）= O（1）

今、方程式を追加して、私は得ています

T（n）= O（1）+ O（1）..。

それで、最終的な答えは何ですか？

4

4 に答える 4

2

で割ることができるたびに関数を1回実行しますn。2これは、log n時間です。

だからあなたは得るO(log n)。

編集：

数値の（基数2の）対数は、を取得するためにn累乗する必要があることです。2n

つまり、指数2^(log n) = nが示されている場合。^

ここで、の近似を計算する簡単な方法は、 whilelog nで除算nすることです。2n > 1

時間を分割kすると、が得られますn < 2^k。

k - 1分割はまだ得られたのでn > 1、あなたも持っていn >= 2^(k-1)ます。

の各メンバーの対数を取ると2^(k - 1) <= n < 2^k、が得られk - 1 <= log n < kます。

于 2011-10-12T15:36:19.900 に答える
1

アルゴリズムはhttp://en.wikipedia.org/wiki/Binary_search_algorithmと非常によく似ています

だから、あなたはそれがなぜであるかについての詳細な説明を読むことができましたO(log(n))

于 2011-10-12T15:39:27.850 に答える
0

マスター定理に精通することをお勧めします。この場合、a = 1、b = 2、f = O（1）です。f = Theta（1）= Theta（n ^（log_2（1）log ^ kn）= Theta（log ^ kn）for k = 0であるため、定理の2番目のケースでT（n）= Theta（log ^（k + 1）n）= Theta（log n）。

非常に便利な定理であり、他のアルゴリズムと比較したり、他の種類の分析を実行したりするのがそれほど簡単ではない場合に役立ちます。

于 2011-10-12T16:15:36.920 に答える
0

重要なのは、条件が満たされるまで、入力が2で除算されるたびです。元。n / 2、n / 4、n / 8 .... n / n

8として入力したとすると、このlog 8の2進数は3になります。したがって、O（logn）になります。定数はカウントされるべきではありません。

それが役に立てば幸い。

于 2015-03-24T19:54:53.733 に答える