Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

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

algorithm - Time Complexity of a loop that integer divides the loop counter by a constant

I'm trying to calculate the time complexity of a simple algorithm in big O notation, but one part of it is seriously boggling my mind. Here is a simplified version of the algorithm:

int a=n
while(a>0)
{
//for loop with time complexity n^3
a = a/8
}

In this instance, it's integer division, so the while loop will terminate after a's value drops below 8. I'm not sure how to express this in terms of n. I'd also like to know how to tackle future calculations like this, where the number of loops isn't too easy to define.

See Question&Answers more detail:os

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

1 Reply

0 votes
by (71.8m points)

I find it easier to do it the other way around in cases like this. What is the opposite of what you're doing (even approximately)? Something like:

for (a = 1; a <= n; a = a * 8)
{
    ...
}

Now, we've changed the while to a for, which has a fixed number of steps, and decrementation to incrementation, which can be easier to work with.

we have:

1, 8, 8^2, ..., 8^k <= n

8^k <= n | apply logarithm

log (8^k) <= log n

k log 8 <= log n

=> k = O(log n)

So your while loop executes O(log n) times. If you have something that is O(n^3) inside, then your entire sequence will be O(n^3 log n).


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...