函數時間複雜度

Question

嗨讀一本調用子例程被認爲是一個常量時間操作的書，即使子例程本身不是在恆定時間內執行，但取決於輸入大小。 然後，如果我有以下的代碼：

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

我想我可以考慮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的函數。

在第二種情況下，技術上時間複雜度是恆定的。

作爲一般性評論，使用漸近表示法指定時間複雜度的要點是描述操作數量作爲輸入大小的函數如何增加。

Answer 2

本書可能的意思是說，調用函數T_func的時間複雜度爲T_call + T_callee。這裏T_call是傳遞參數併爲被調用者設置環境的時間操作，T_callee是子程序內部花費的時間。該書說，假設T_call是恆定的，但對T_callee沒有這樣的假設是可以接受的。

澄清假設我們有一個功能func調用一個子程序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))。