这个递归算法的复杂度是多少

Question

如何计算像这样有点复杂的递归算法的复杂度在这种情况下，something(0,n)

的复杂度是多少？

void something(int b, int e) {
     if (b >= e) return;
     int a = 0;
     for(int i=b; i < e; i++)
     a++;
     int k = (b+e)/2;
     something(b, k);
     something(k+1, e);
     }

我试图分析这个算法，认为它的复杂度是n*ln(n)，但仍然无法得到正式证明。

Answer 1

最初，循环将运行进行 (e-b) 次，它会调用自身 2 次，但将循环的大小减少一半

因此，((e-b)/2) 将运行进行 2 次迭代；一次 (b,(b+e)/2) 一次 ((b+e)/2+1,e)

同样，两次迭代都会再次调用自己 2 次，但将迭代长度减少一半。

所以 `((e-b)/4) 将运行 4 次，依此类推。

递归树的高度将为log(b-e)，（每个节点有2个子节点）

所以，time complexity = (b-e) + 2*((b-e)/2) + 4*((b-e)/4) + .....(log(b-e) times)

此表达式的计算结果为 (b-e)*log(b-e)

因此，时间复杂度=O(nlogn)

这个递归算法的复杂度是多少

What would be complexity of this recursive algorithm

time-complexity

code-complexity