for(int j=1; j<=n; j*=2)
这个循环最终执行的次数假设为x,则x次的时候j=2^x 。
当j>n时停止执行,于是2^x>n ,则可以认为该循环一共执行了log2(n)次。
所以该循环的时间复杂度为o(log2(n)),简记为o(log n) ,忽略掉2的底数。
方法:
1、首先,看外循环for(i=0;i<n;i++),按照i++的递加速度,直到这个循环退出,一共是n次。
2、再看内部循环,for(j=1;j<n;j*=2),这个内部循环的累加速度是j=j*2,假设循环x次之后,这个循环退出,2^x>n===》x=log2(n)。
3、如果把两个循环合在一起看,也就是一共循环了n个x次,也就是log2(n)。