ビッグO表記Python関数

Question

foo（A）関数の大きなOは何ですか？（nはAの長さに等しい） 私がfoo（4）ステートメントが再帰の各反復に対してO（1）であると言うことができる限り。また、私はfoo（A // 8）文の実行時間が対数であることを理解しています。

したがって、プログラムの実行時間はbigO（log（n））になりますか？

この機能は、テストの実行時間を実践するために使用されます。

def foo(A): 
    if A <= 6: 
     return 7 
    return foo(A//8) + foo(4) 

Answer 1

あなたの分析は正しいです。 foo(4)は一定の時間がかかり、log n（ベース8）回の操作を実行する必要があります。これはもちろんO(log n)です。

数式を使用する方が快適な場合は、Master Theorem（a = 1、b = 8、k = i = 0）で確認してください。

Answer 2

あなたのプログラムは、以下のrecurrsionのように書くことができます= 1、およびb = 8

我々は後者の場合に陥るところ

T(n) = T(n/8) + C 

はMaster theoremの適用：

n^(log(1) base 8) = n^0 = 1 
C = ϴ(1). 
==> T(n) = O(n^(log(a) base b) * log(n)) = O(n^(log(1) base 8) * log(n)) 
     = n^0 * log(n) = 1*log(n) = O(log(n)) 

Answer 3

Aはベクトルではなく整数なので、n o Nこの問題の複雑さはAの観点から述べなければなりません。

は、私たちはA=1000と実行をシミュレートしてみましょう：

foo(1000) 
    calls foo(125) and foo(4), i.e. 
    calls foo(15) and foo(4), and foo(4), i.e. 
    calls foo(1) and foo(4), and foo(4), and foo(4). 

あなたがパターンを取得します。したがって、fooへの間接呼び出しの総数は、Aを8で除算できる回数が6以下になるまで、最終コールに加算されます。

これはまさにFloor(Log8(Ceil(A/7)))+1であり、確かにO(Log(A))です。ちょうど楽しみのため

---

：

あなたが進（基数8）でAを書く場合、機能fooは7回8進数の合計が、右端のを計算し、プラス7または14（最後の場合数字は7です）。