再帰によるBig O表記の計算

Question

私はBig O Notation最悪の場合の実行時間を理解しようとしています。 しかし、私はまだそれをかなり理解していません。

これは私が最近書いたいくつかのコードです：

def g(n): 
    if n==0: 
     return 1 
    elif n==1: 
     return 2 
    else: 
     n_div=n//2 
     n_mod=n%2 
     return g(n_div)*g(n_mod) 

をだから私は、私は、少なくともその権利だことを願っています：

def g(n): 
    if n==0: 
     return 1 

と：

elif n==1: 
    return 2 

はOです（1）のように一定である。

しかし、else部分はどうですか？

私が選んだnに依存しているのでO（n）ですか？

else部分のBig Oの複雑さは誰でも説明できますか？

Answer 1

さて、関数を3つのケースに分けることができ、最初の2つがO（1）であることが既に分かっています。 3番目の方がやや難しいですが、2つの部分に分けることもできます。私たちは、すぐにn%2が再び最初2例1を解決します0または1、のいずれかを評価することを見ることができますので、我々はそれを無視することができます

g(n//2)*g(n%2) 

：から

再帰が明確に発生します。 g(n//2)にお越しください。あなたは用語が半分ずつ減少し、同じ再帰で発生見ることができるように

>>> n = 37 
>>> while n > 1: 
...  n //= 2 
...  print(n) 
... 
18 
9 
4 
2 
1 

：印刷ループとしてこれを書き換えると、出力を調べることによって、あなたは何かに気付くでしょう。これは、対角のです。

この結果、この関数の最悪の場合はO（logn）になります。

lognが実際にBig-O表記で意味することについては、this questionをご覧ください。

Answer 2

O表記は実際にはプログラムの一部ではありません。入力サイズが大きくなると実行時間が長くなる方法を実際に測定します。この場合、時間のかかる部分は最後のelse部分です。

あなたのプログラムでこれがどのように機能するかを知る必要があります。ここでは、あなたに役立つ簡単な実証分析があります。与えられた入力に対して最後のelse部分が何回実行されたかを印刷するために少しプログラムをインストルメントすると、これが表示されます。

n | times 
-----+----- 
    2 | 1 
    4 | 2 
    8 | 3 
    16 | 4 
    32 | 5 
    64 | 6 
128 | 7 
256 | 8 
512 | 9 
1024 | 10 
2048 | 11 
4096 | 12 
8192 | 13 

これをプロットすると、次のように表示されます。

あなたは、入力のサイズが大きくなると、呼の数も直線的に増加するが、サブことがわかります。あなたのnがループの各繰り返しを50％減らすので、実際には対数関数です。