步长递增的while循环迭代次数

Question

在我的一个作业练习中，我需要计算一个算法中的步骤数量，并证明一个紧密的界限，但我就是无法找到一个准确的公式来表示这个循环在大小为n的列表中迭代的次数。

n = len(A)
value = 0
index = 0
step = 1
while index < n:
    value = A[index] - value 
    index = index + step 
    step = step + 1

这里的步骤在每次迭代时增加1，所以索引不会线性增加。我在找一个公式来表示它是如何增长的。如果我查看一个关于迭代次数与大小n的表格，它看起来像是以平方根n的速度增长，但我找不到更精确的东西来描述确切的迭代次数。

有没有人能帮我或者给我指个方向？

Answer 1

你的循环会一直运行，只要 index < n（我知道你明白这个，耐心点）。

可以把 index 看作是一个序列

I = 0 , 1 , 3 , 6 , 10 , 15

其中每个项都是前一个项加上从起点的距离：index = index + step。用数学的方式可以写成

S = 0, 1, 3, 6, 10 ..... I(k-1), I(k) 
    ^^^^^^^^^  k terms ^^^^^^^^^^^^^^

这里

I(k) = I(k-1) + k

而 I(k) 接近 n（数组 A 的长度）的速度就是我们想要的复杂度（我相信你在课堂上解决过类似的问题，所以才会有这样的作业）。

Answer 2

这里有一些代码可以帮助你进行探索：

def calls(n):
    index = 0
    step = 1
    call = 0
    while index < n:
        index += step 
        step += 1
        call += 1
    return call

UPTO = 500        
for i in range(1, UPTO):
    print("{:>4}: {}".format(i, calls(i)))

这段代码的结果是：

   1: 1    # 1 1    
   2: 2
   3: 2    # 2 2s
   4: 3
   5: 3
   6: 3    # 3 3s
   7: 4
   8: 4
   9: 4
  10: 4    # 4 4s
  11: 5
  12: 5
  13: 5
  14: 5
  15: 5    # ...
  16: 6
# etc

编辑：好的，下一步：我们可以看到

calls(n) == k such that (k - 1) * k / 2 < n <= k * (k + 1) / 2

(k 是满足 2 *n <= k * (k + 1) 的最小整数)

我们可以引入一个叫做 delta 的东西，使得 0 <= delta < 1，然后设 k' = k - delta，并且 2 * n == k' * (k' - 1)；接下来求解 k'，最后得到 k = ceil(k')，证明完毕。