关于'平方根的时间复杂度的Python代码示例[关闭]

Question

我在学习不同的大O时间复杂度，最后一个我是“平方根”，但我似乎无法找到它使用一个简单的算法用于证明这个时间复杂度任何有用的Python代码片段。

我觉得更容易理解这些复杂的时候，我可以看到一个简单的（即使不现实）代码段。

Answer 1

一个很好的例子是找出一个号码的所有约数。因为如果i是n的除数，n/i也是n你只需要循环，直到n的平方根，找出它的所有约数的约数。

import math

def get_divisors(n):
    m = 1 + int(math.sqrt(n))
    divisors =  []
    for i in range(1, m):
        if n % i == 0:
            divisors.append(i) 
            if i != n//i:   # prevent counting twice for square numbers
                divisors.append(n // i)
    return divisors
print(get_divisors(100))  # [1, 100, 2, 50, 4, 25, 5, 20, 10]