关于#时间复杂度#的问题，如何解决？

下列程序段的时间复杂度是



int  sum = 0;
for(int i=1;i<n;i*=2)
    for(int j=0;jsum++;

A.
O(logn)

B.
O(n)

C.
O(nlogn)

D.
O(n
2
)

C
外层是logn，内层是n

B，是O(n)的。

设2^k<=n<2^(k+1)，其中k的值随n而定

则题意即求1+2+4+...+2^k=2^(k+1)-1

2^(k+1)-1最多为2^k的两倍不到，即n的两倍不到

所以时间复杂度为O(n)