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
}

我想我可以认为 func() 是一个常数时间函数，例如 O(1)？

如果我有这个怎么办：

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

我还能认为 func() 是一个常数时间函数吗？在某些情况下这条规则适用吗？谢谢！

score 0 · Accepted Answer

不，您不能考虑func(int m)具有恒定的时间复杂度。它的时间复杂度是O(T1(m) + T2(10)), 其中T1和T2是分别描述和时间复杂度的subrout函数subrout2。

在第二种情况下，时间复杂度在技术上是恒定的。

作为一般评论，使用渐近符号指定时间复杂度的目的是描述操作数量如何作为输入大小的函数而增加。

score 0 · Accepted Answer

这本书的意思可能是调用函数的时间复杂度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))。

2 回答 2