Question

算法时间复杂度问题，题目如下，谢谢！

假设int类型的数组a含有n+1个元素，函数f的定义如下，那么，求f(0)的时间复杂度T(n)

void f(int j)
{
int tem;

if(j < n){

if (j != 0) for(int i = j; i <= n; i *= 2) {temp = a[i]; a[i]=a[j];a[j]=temp;}
j++;

f(j);

}

}

Answer 1

楼主你好
大致是这样:
首先说:
for(i=1;i<=n;i*=2)
语句;
这个的循环的执行的次数
是:
og2 (n-1 +1)
log以2为底 n的对数 + 1

那么把 i=1换做j j是从1~n-1 因为 当j为n时函数结束

因此运行的次数就是：
j:1~n-1
(log2 (n-j+1))+1 的和
就是:
log2 (n!) +n

希望能帮助你哈