递归循环时的时间复杂度
递归循环时的时间复杂度
提问于 2020-01-26 05:14:48
void call(int n)
{
for (int j=1;j<=n;j++)
{
call(n/2);
}
}
void main()
{
int i;
for (i=1;i<=n;i++)
{
call(i);
}
}因为这个循环的时间复杂性。这个思维过程正确吗？在主函数中，循环是O(N)。在调用函数中，循环为O(N)，递归为n/ 2，因此O(LogN)的基值为2。因此，总体时间复杂度为O(N)*O(N)*O(LogN)= O(N^2 LogN)？
回答 1
Stack Overflow用户
回答已采纳
发布于 2020-01-26 20:46:17
可以使用递归树计算调用数，递归函数的顺序等于递归树中的节点数(叶是未显示的调用(n/2))：
因此，要计算所有节点的数目，您可以计算和，并估计顺序(使用几何序列公式计算和)：
主回路的阶数小于
，所以主循环顺序是
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/59915760
复制相关文章
相似问题
腾讯云开发者
