Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
2.0k views
in Technique[技术] by (71.8m points)

algorithm - If an inner loop is incremented by squaring the variable, what will be the runtime of it and how?

Say if n here is any number less than 256 the inner loop is going to be true for 4 times, now what kind of sequence does the inner loop follow as n increases.

for ( int i=1; i<=n; i++){
    for ( int j=2;j<=n; j=j*j){

    }
}

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Answer

0 votes
by (71.8m points)

The outer loop will be iterated n times. The inner loop each time squared the previous value, i.e., 2 + 2^2 + 2^4 + 2^8 + ... + 2^{2^k}. Hence, the time complexity is n * k. To compute the k, we need to find a k such that n = 2 + 2^2 + 2^4 + 2^8 + ... + 2^{2^k}:

2 + 2^2 + 2^4 + 2^8 + ... + 2^{2^k} = sum_{t=0}^{k} 2^{2^t} = n 
=>  k = heta(log(log(n)) 

Therefore, the time complexity if Theta(n log(log(n))).


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...