complexity-theory - 特定の擬似コード アルゴリズムの複雑さ

Question

私は自分のデータ構造とアルゴリズムの最終的な勉強をしているところです。次の質問は私の中間試験で、間違っていたので、それを理解しようとしています:

次の疑似コードの複雑さは?

 x <- 0
 for x <- 0 to n:
   for y <- 0 to n:
     y <- y + 1
     y <- y * 2

中間テストでは O( n^2 ) と答えましたが、今改めて見ると O( nlogn ) かもしれないと思います。

正解は？

どんな助けも試験に合格するのに役立ちます!

乾杯！

Answer 1

以下は、現時点での私の答えです...

外側のループfor x <- 0 to nは確実に n 回実行されます。

内側のループfor y <- 0 to nは n 回実行されるように見えますが、実行されるたびに、そこに含まれるコードによって y が指数関数的に n に近づきます。したがって、コードのこのセクションは O( logn ) の複雑さで実行されると思います。

したがって、アルゴリズム全体が O( nlogn ) 時間の計算量で実行されます。

Answer 2

経験的に、私はあえてあなたのアルゴリズムの振る舞いを次のように表現するかもしれません:

一部のスナップショット (「合計」は反復回数):

500 * 8 = 4000

対数計算機 リンク