为什么用大O表示的结果是O(nlogn)?

Question

for j := 1 to N do
begin
i := 2
while i < N do
begin
A[i] := i
i := i * 2
end;
end;

Answer 1

的确是O(nlogn)
for j := 1 to N do  循环 n
while i < N 循环 logn一共是 O(nlogn)

Answer 2

这样满足i<n的次数有多少次呢？
因为i一定是2的倍数，所以如果i=2^m的话，m即循环次数
假设2^m<n<2^(m+1)
于是m<logn<m+1,所以m=logn取整
所以内循环是logn

Answer 3

外循环是N，
内循环是x^2=N 所以是logN，
所以就是O（nlogn）了