循环函数的运行时间

int foo(int n) 
{ 
    if(n==0) 
     return 1; 
    int sum = 0; 
    for(int i = 0;i < n;i++) 
     sum += foo(n-1); 
    return sum; 
}

最近我在学Big O notation。有人可以给我一个关于如何通过使用大O符号以及如何呈现此函数的运行时来确定此循环函数的运行时的想法。循环函数的运行时间

来源

2017-03-01 CDY

所以想想如果你为大n运行foo（n）会发生什么。然后该总和包含n次对foo（n-1）的调用。在递归树的下一层，我们有foo（n-1），我们再次调用n（-1）次foo（n-1-1），但是对于我们树的n foo（n-1）个分支。我们知道树的高度为n，因为我们必须去foo（n-n）。所以在每个递归步骤中，将foo的一个实例转换为foo（n-1）的O（n）个实例。

我不确定如果我应该透露答案，因为它看起来像一个练习，但它似乎退出显而易见，只需绘制递归树的几个级别，并找到您的答案。

来源

2017-03-01 11:26:36 gue

假设我假设n = 3，那是你提到的递归树吗？ http://imgur.com/a/lusID – CDY

不，但接近。考虑for循环，递归调用sum + = foo（n-1）不依赖于循环变量i。因此，在树中的每个节点上，我们分支n次，但每个叶子都用n-1调用。 http://imgur.com/a/K9g8z – gue

谢谢，我明白了。你解释的很容易理解。 – CDY

循环函数的运行时间

回答

相关问题