この関数の大きなO表記は何ですか？

result = 0 
i = 0 
while i < 2**n: 
     result = result + i 
     i += 1 
# end while

私はO（2^n）と仮定しています。 Pythonコード。この関数の大きなO表記は何ですか？

出典

2016-12-09 Bob Marley

私はPythonに参加していません。 '2 ** n'は' 2^n'を意味しますか？もしそうなら、実行時間は 'O（2^n）'です。 – Codor

はい、それは@Codorが言うように2^nです。どのように計算されているか興味があれば、これを見てください - http://stackoverflow.com/a/4852666/4481312 – marmeladze

@melpomene： '2 ** n'は* shift *：' 2 ** n'を必要とします== '1 << n'; 'n'はループ内で変化しないので、' 2 ** n'は再計算されません。 –

2^nを計算しているので、コードの時間複雑度はO(2^n log n)だと思います（2^n回）。
a^bO(log b)でexponentiation by squaringを計算することができます。私は、pythonの指数アルゴリズムはO(log n)アルゴリズムだと思います。
したがって、時間の複雑さはO(2^n log n)です。

出典

2016-12-10 05:57:15 square1001

あなたは累乗が重要な時間を要するかもしれないことは間違いありませんが（おそらく対数であり、おそらくは一定時間のビットシフトです）、全体的な複雑さのクラスは可能な限り基本的なものとして最善のものになります。この場合は 'O（2^n * log n ）== O（2^n） 'である。小さな魚は気にしない – progo

この関数の大きなO表記は何ですか？

答えて

関連する問題