big-o - この関数の計算量はどれくらいですか?

Question

この関数の計算の複雑さはどうなるのだろうと思っていましたか?

2^(ログ(n)-1)

対数は底 2 です。

Answer 1

すべての対数と累乗を計算するアルゴリズムを使用するかどうかによって異なります。この関数が本質的に 2 による除算であることに気付くほど賢い場合はO(1)、右シフトを行うことにより、整数に対して定数時間 (つまり ) でこれを実装できます。