派生一个 while 循环在 $\Theta( \sqrt{n} )$ 中运行

Question

我知道算法 A 在 $\Theta(\sqrt{n})$ 中运行，但如何得出这一事实？

算法A

i = 0
s = 0
while s <= n:
    s += i
    i += 1

这是我的想法。我们知道 A 的上限为 O(n)，因为我们在每次迭代中将 $s$ 递增超过 1。我们还知道它必须以 $\log n$ 为下界，因为我们在每次迭代中将 $s$ 递增小于 $2^i$。（如果我错了，请纠正我，这些只是我的想法......）。

现在，关于 A，我们还能说些什么？我们如何得出它的时间复杂度是 $\Theta(\sqrt{n})$?

Answer 1

为了帮助您进行推理，您可以进行实验测试来计算迭代次数。例如：

for n in range(100000000, 1000000000, 100000000) :   
    i = 0
    s = 0
    while s <= n:
        s += i
        i += 1

得到如下结果：

    n       | iterations|   sqrt(n)
-------------------------------------
100000000   |   14143   |   10000.00
200000000   |   20001   |   14142.14
300000000   |   24496   |   17320.51
400000000   |   28285   |   20000.00
500000000   |   31624   |   22360.68
600000000   |   34642   |   24494.90
700000000   |   37418   |   26457.51
800000000   |   40001   |   28284.27
900000000   |   42427   |   30000.00

编辑

@WillNess推荐你可以了解更多here

Answer 2

从代码中可以看出s = 1 + 2 + 3 + .... + i（1）和s <= n（2）。第一个等式也可以写成s = i * (i + 1) / 2，这意味着在i中大约是sqrt(s * 2)和sqrt(n * 2)，从代码中我们可以看到while循环运行 i 次，每次进行 O(1) 次计算。因此整体复杂度为 O(sqrt(n))

Answer 3

每次我们增加 i，我们将 s 添加到 i。这意味着在 k 步之后，s 已经增长到：

     k
    ---
    \
s = /   i
    ---
    i=0

这个序列是已知的。在第 k 步之后，有 T_k 个数字，其中 T _k一个triangular number [wiki]。 T_k 的较短公式是 T_k=i×(i+ 1)/2。 T_k 因此缩放二次与 k.

当T_k高于n时，该过程将停止。因此我们可以确定：T_k > n，因此 k×(k+1)/2 > T_k 因此 k²/2 + k/2 - n > 0.这是一个二次方程，判别式 d = 1/4 + 2×n，因此（正）解为 k₀=-1/2 + √d。因此它与 √2n.

成比例

派生一个 while 循环在 $\Theta( \sqrt{n} )$ 中运行

Derive a while loop runs in $\Theta( \sqrt{n} )$

python

complexity-theory

time-complexity

编辑