如何到达循环的log（n）运行时间？(How to arrive at log(n) running time of loop?)

如何到达循环的log（n）运行时间？(How to arrive at log(n) running time of loop?)

在每次迭代时将变量乘以/除以常数因子的循环被认为在O（log（n））时间内运行。

例如：

for(i=1; i<=n;i*2){ --some O(1) operations ... }

如何计算或确定此循环将运行log（n）次？

我之前解释过，变量被分割/相乘的因子将是日志的基础。

我理解运行时间及其含义，我只是不理解达到这个特定解决方案所需的数学/推理。 如何知道循环从i = 1到i = n每次乘以2，从数学上得出这个解？

（我试图理解这是理解如何通过恒定功率增加变量导致log（log（n））的运行时间的基础。）

A loop whose variable is multiplied/divided by a constant factor at each iteration is considered to run in O(log(n)) time.

for example:

for(i=1; i<=n;i*2){ --some O(1) operations ... }

How do I calculate or establish that this loop will run log(n) times?

I was previously explained that the factor by which the variable is divided/multiplied will be the base of the log.

I understand running times and their meanings, I just do not understand the math/reasoning that is required to arrive at this particular solution. How does one mathematically arrive at this solution from knowing that the loop runs from i=1 to i=n multiplying i by 2 each time?

(I am trying to understand this as a basis to understanding how increasing the variable by a constant power leads to a running time of log(log(n)).)

最满意答案

这就是我自己理解它的方法：尝试用函数f(x)来建模for循环，这样在for循环的第x ^次迭代中，你的迭代器i=f(x) 。 对于for(i=0;i<n;i++)的简单情况，很容易看出，对于每1次迭代，我上升一，所以我们可以说f（x）= x，在x ^th循环的迭代，i = x。 在第0 ^次迭代时i = 0，在第一次i = 1时，在第二次i = 2上，依此类推。

对于另一种情况， for (i=1;i<n;i*=2) ，我们需要得到一个f（x），它将模拟这样的事实：对于每^第 x ^次迭代，i加倍。 连续加倍可以表示为2的幂，所以令f(x)=2^x 。 在第0 ^次迭代中，i = 1，并且2 ^ 0 = 1。 在第一个，i = 2，并且2 ^ 1 = 2，在第二个，i = 4，并且2 ^ 2 = 4，然后i = 8,2 ^ 3 = 8，然后i = 16，并且2 ^ 4 = 16。 所以我们可以说f(x)=2^x准确地模拟我们的循环。

为了确定循环完成达到某个n所需的步n ，求解方程f(x)=n 。 使用16的示例，即for (i=1;i<16;i*=2) ，它变为f(2^x)=16 。 log ₂ （2 ^ x = 16）= x = 4，这与我们的循环在4次迭代中完成的事实一致。

This is how I make sense of it myself: Try to come up with a function f(x) to model your for loop, such that on the x^th iteration of your for loop, your iterator i=f(x). For the simple case of for(i=0;i<n;i++) it is easy to see that for every 1 iteration, i goes up by one, so we can say that f(x)=x, on the x^th iteration of the loop, i=x. On the 0^th iteration i=0, on the first i=1, on the second i=2, and so on.

For the other case, for (i=1;i<n;i*=2), we need to come up with an f(x) that will model the fact that for every x^th iteration, i is doubled. Successive doubling can be expressed as powers of 2, so let f(x)=2^x. On the 0^th iteration, i=1, and 2^0=1. On the first, i=2, and 2^1=2, on the second, i=4, and 2^2=4, then i=8, 2^3=8, then i=16, and 2^4=16. So we can say that f(x)=2^x accurately models our loop.

To figure out how many steps the loop takes to complete to reach a certain n, solve the equation f(x)=n. Using an example of 16, ie for (i=1;i<16;i*=2), it becomes f(2^x)=16. log₂(2^x=16) = x=4, which agrees with the fact that our loop completes in 4 iterations.