python - 为什么这两个平方根算法的运行方式如此不同，尽管它们应该完全相同？

Question

我正在使用 Python 编写代码，学习计算机科学，我决定在看到解决方案代码之前尝试解决正在解释的其中一个问题。

然而，我编写的解决方案代码虽然运行良好，但需要 50813497 次迭代(即近 5100 万次)来计算 49 的平方根，而解决方案中给出的代码仅需要 54 次迭代即可实现一样。

这是我的代码:

def ssqrt(x):
    origx = x
    epsilon = 0.000001
    num_guess = 0
    while abs((x/2)**2 - origx) >= epsilon:
        #print(x)
        num_guess+=1
        if (x/2)**2 >= origx:
            x = x/2
        elif (x/2)**2 <= origx:
            x = (3/2)*x

    if abs((x/2)**2 - origx) < epsilon:
        print(num_guess)    
        return x/2
y = ssqrt(49)
print(y)

这是解决方案代码:

x = 49
low = 0
high = x
ans = (low+high)/2
epsilon = 0.00000000000001
num = 0
while abs(ans**2-x) >= epsilon:
    num += 1
    if ans**2 < x:
        low = ans
    else:
        high = ans
    ans = (high+low)/2
print (num)
print (ans)

现在，我明白我的是一个函数，解决方案中给出的代码不是一个函数，但总体思路是我们正在尝试实现二分搜索算法。这就是我想要达到的目的。

请帮忙。

(仅供引用，这是在 edX 类(class)中讲授的，Introduction to Computer Science and Programming Using Python)

Answer 1

进一步解释@Jkind9 所说的内容，给定的解决方案使用二进制搜索，每次迭代将搜索空间减半，从而以对数运行时间执行。如果一次二进制迭代的搜索空间是 [low, high] ，下一次迭代的搜索空间将是 [low, (low + high) / 2]或 [(low + high) / 2, high] ，有效地将 future 迭代中需要观察的元素数量减半。结合每次迭代只检查一个元素(中间元素)这一事实，二分查找的运行时间因此是O(log2 n)。 , 其中n是要搜索的元素数。

但是，您的算法不会每次都将搜索空间减半；您只需平均搜索完全相同的范围。以类似二进制搜索的方式(具有下限和上限)重新解释您的算法，每次迭代的搜索空间可以视为 [0, x] (让 n 成为该范围内要检查的数字的数量)，其中 x / 2是每次迭代检查的元素。下一次迭代的搜索空间为 [0, x/2]。 ( n/2 数字)或 [0, 3x/2] (3n/2 数字)。因此，下一次迭代的搜索空间为 (n/2 + 3n/2)/2 = n。平均数字，使您的算法平均具有线性时间复杂度(实际迭代次数可能或多或少取决于输入和算法在分支中采用的路径)。

这也可以通过使用输入查找迭代次数来验证；当您的算法的任务是找到 49 的平方根且 epsilon 为 0.000001 时，它必须大致查看 49 / 0.000001。 = 49,000,000 个号码来找到正确的号码。如果算法的平均时间复杂度为O(n) ，可以合理地估计平均需要大约 49,000,000 次迭代才能找到这个平方根。实际进行的迭代次数为 50,813,497，与我们的估计相差不远(相对误差:3.7%)。同样，对于给定的 epsilon，二分搜索算法必须查找大约 4.9e15 个数字。鉴于二分查找的时间复杂度为O(log2 n) , 迭代次数应为 ceil(log2(4.9e15)) = 53，这又非常接近实际进行的迭代次数 (54)。