Function Time Complexity

Question

こんにちは、あるサブルーチンが一定時間では実行されずに入力サイズに依存していても、呼び出しサブルーチンは一定時間操作と見なされます。私は次のコードがある場合 次に：

void func(int m){ 
int n = 10; 
    subrout(m);//function which complexity depends on m 
    subrout2(n);//function which complexity depends on n 
} 

を私は（iはFUNCを考慮することができると仮定）は、例えば、一定時間の関数であることがO（1）？

と私は、この持っている場合：

void func(){ 
    int n = 10; 
    Type object; 
    object.member_method(n);/*member function which time complexity depends upon n*/ 
} 

私はまだFUNC（）一定の時間関数を考慮することができますか？ このルールに該当する場合がありますか？感謝！ ありがとう！

Answer 1

いいえ、func(int m)は一定の時間の複雑さを持つとはみなされません。その時間複雑度はO(T1(m) + T2(10))であり、T1およびT2は、それぞれsubroutおよびsubrout2の時間複雑度を説明する関数です。

第2のケースでは、時間的複雑さは技術的に一定です。

一般的なコメントとして、漸近表記による時間の複雑さを指定するポイントは、入力サイズの関数として操作の数がどのように増加するかを記述することです。

Answer 2

本書ではおそらく、呼び出し元関数T_funcの時間の複雑さはT_call + T_calleeです。ここではT_callは、パラメータを渡して呼び出し先の環境を設定する時間オペレーションであり、T_calleeはサブルーチン内で費やされる時間です。この本によれば、についてはそのような前提はないが、T_callが一定であると仮定することは安全であるという。

明確にするために、funcという関数があり、それは1つのサブルーチンcalleeを呼び出します。

func(s){ 
     callee(s); 
    } 

次にT_func(s) = T_call + T_callee(s)。 size(s) = nとT_callee = O(f(n))の場合は、T_func = O(f(n))と言うのが安全です。