if条件下函数的时间复杂度
if条件下函数的时间复杂度
提问于 2015-07-09 00:15:12
这类if语句的时间复杂度是多少？
考虑以下时间复杂度: func1 = O(n)和func2 = O(n)
if(func1())
{
return func2();
}时间复杂度是O(n^2)还是O(n)？
回答 3
Stack Overflow用户
发布于 2015-07-09 00:17:23
它将是O(n)，因为O(n)+O(n) = 2 O(n)= O(n)
Stack Overflow用户
发布于 2015-07-09 00:17:58
只要这不是在循环中运行(就像在此语句中执行一次一样)，复杂度为O(n) + O(n) = 2O(n) = O(n)摊销
Stack Overflow用户
发布于 2015-07-09 00:26:33
因此，以下是步骤：
1)执行func1并返回
2) func2可能会被执行并返回
正如您所看到的，每个函数在另一个函数开始之前返回，这意味着添加了时间。在计算O时，除了最大的次数，即O(n)之外，所有相加的次数都会被丢弃。
作为一个反例，获得O(n^2)的方法如下
func1(func2)
其中func1将其参数执行大约n次。这意味着时间是成倍的。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/31298166
复制相关文章
相似问题
腾讯云开发者
