时间复杂度是O（N）还是O（Log N）？ [英] Is Time complexity O(N) or O(Log N)?

问题描述

i = 1;
while(i<N) {
   i*=2;
}

我认为上述代码的时间复杂度为O（N），但我我不确定。您能否让我知道您是否认为它的O（Log N）及其原因？

I think the time complexity of the above code is O(N) but i'm not sure about it. Can you please let me know if you think its O(Log N) and the reason?

推荐答案

时间复杂度si与数字成正比的周期。并且循环数完全等于 Log（N）/ Log（2），其中Log是任何对数。或者只是 Log2（N），其中Log2是以2为底的对数。因此，它是O（Log N）。

Time complexity si proportional to number of cycles. And number of cycles is exactly equal to Log(N)/Log(2), where Log is any logarithm. Or just Log2(N), where Log2 is logarithm with base 2. It is therefore O(Log N).

这篇关于时间复杂度是O（N）还是O（Log N）？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！