函数时间复杂度

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))。