运行嵌套while循环次数

Question

Function f(n)
    s = 0
    i = 1
    while i < 7n^1/2 do
        j = i
        while j > 5 do
            s = s + i -j
            j = j -2
        end
        i = 5i
    end
    return s
end f

我正在尝试用上面的代码解决大 theta 的运行时间问题。我一直在到处寻找可以帮助我举个例子的东西，但一切都是 for 循环或只有一个 while 循环。你会如何使用嵌套 while 循环解决这个问题？

Answer 1

第一个循环将执行 7 * sqrt(n) 次迭代。指数 1/2 与数字的 sqrt() 相同。

第二个循环将运行 m - 2次，因为i的前两个值分别是1和5，没有通过比较。

i 的增量为 5i。

举个例子 n = 16:

i = 1, n = 16;
while( i < 7 * 4; i *= 5 )
    //Do something

First value of i = 1. It runs 1 time. Inside loop will run 0 times.
Second value of i = 5. It runs 2 times. Inside loop will run 0 times.
Third value of i = 25. It runs 3 times. Inside loop will run 10 times.
Fourth value of i = 125. It stops.

外部迭代是 n 次迭代，而内部迭代是 m 次迭代，这给出 O( 7sqrt(n) * (m - 2) )

IMO，很复杂。

Answer 2

让我们将其分解为两个关键点：

i从1开始，自乘5，直到大于等于7 sqrt(n)。这是对数步数的指数增长。因此我们可以将代码更改为以下等效代码：
```
m = floor(log(5, 7n^(1/2)))
k = 0
while k < m do
   j = 5^k
   // ... inner loop ...
end
```
外层循环的每一次迭代，j从i开始，递减2，直到小于等于5.请注意，在第一次执行外层循环i = 1时，在第二次i = 5中执行，因此直到第三次迭代才执行内层循环。循环限制是指如果k为奇数，则j的最终值为7，如果为偶数，则为6（您可以用笔和纸检查）。

结合以上步骤，我们得出：

运行嵌套while循环次数

Running time of nested while loops

big-o

runtime

while-loop

运行 嵌套while循环次数

Running time of nested while loops

big-o

runtime

while-loop

运行嵌套while循环次数