if条件下函数的时间复杂度

Question

这类if语句的时间复杂度是多少?

考虑以下时间复杂度:func1 = O(n)和func2 = O(n)

if(func1())
{
   return func2();
}

时间复杂度是O(n^2)还是O(n)?

Answer 1

结果为0 (n)，因为O(n)+O(n) = 2 O(n)= O(n)

Answer 2

只要不是在循环中运行(如在此语句中只执行一次)，复杂度为O(n) + O(n) = 2O(n) = O(n)平摊

Answer 3

步骤如下:
1)执行func1并返回
2) func2可能被执行并返回

可以看到，每个函数在另一个函数开始之前返回，这意味着时间被添加了。在计算O时，除了最大的O(n)外，可以省略所有相加的时间。

作为反例，得到O(n^2)的一种方法是
func1 (func2)
其中func1执行它的参数大约n次。