algorithm - アルゴリズムのメモリと時間の複雑さを決定する方法は?

Question

私は時間とメモリの複雑さを判断するのが苦手で、誰かが私を助けてくれれば幸いです.

ここにアルゴリズムがありますが、その時間とメモリの複雑さがどうなるかわかりません。

Function sample(k)
   IF k < 2
       Return 0
   Return 1 + sample(k/2)

その時間とメモリの複雑さとは何ですか?またその理由は?

ありがとう

Answer 1

あなたは実際に log_2(k)、底 2 の対数を見ています。底を変更するには、定数を掛ける必要があります。とにかく定数を掛けるので、O(log(n))、O(ln(n))、O(log_2(n)) はすべて同じです。

では、なぜ上記の方法は基数 2 の対数複雑度を持つのでしょうか? 呼び出しごとに k を半分に分割しています。逆に行くと、呼び出しごとに 2 を掛けることになります。2 を掛けることは 2^n であり、log_2(n) はまさにその逆数です。

二分木を描くと役立つかもしれません。n 個のノードを持つツリーの高さは log_2(n) であり、高さ n のツリーは 2^n ノードです。