algorithm - 这个用于计算数字平方根的特定(坏)算法的渐近复杂度是多少？

Question

偶然发现了一个计算数字平方根的(糟糕的)算法。陷入了关于时间复杂度的小争论。我断言时间复杂度是 O(n^2) 因为对于 n 个输入，它将被乘以 n 次。我的 friend 断言时间复杂度实际上是 O(n)。谁是对的，为什么？

def squareRoot(x):
if x<0:
    return "undefined"
elif x==0:
    return 0
for i in range(0,x):
    if(i*i)==x:
        return i

Answer 1

它是 O(n)，因为在最坏的情况下，您执行 x 次乘法和测试，因此您的计算时间与您的输入呈线性增长。