这种递归算法的复杂性是什么

Question

如何在这种情况下计算这样一个复杂的递归算法的复杂性，这将是某些东西的复杂性（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）