python - 得到 n 的所有约数的这个算法的运行时间复杂度是多少？

Question

def get_submultiples(n):
    # Get all submultiples of n
    if n == 1:
        return [1]
    i = 2
    submultiples = set([1,n])
    m = n
    while i < m:
        if n % i != 0:
            m = int(n/i)+1
        else:
            submultiples.add(i)
            submultiples.add(int(n/i))
        i += 1
    return submultiples

这个算法是我自己写的，我想知道它的O(?)是多少。有谁能够帮助我？

它由python编写，“n”是一个整数。

Answer 1

Big-O 复杂性因您有条件地收缩而变得复杂 m .更多因素n有，收缩的次数越少m .如果它的因素很少，则复杂度接近 O(√n)，但如果它有很多因素，则复杂度接近 O(n)。我不知道对于 n 的任意值是如何产生影响的。 .
您可以通过缩小 m 来改善这一点。每次迭代，无论是否i是一个因素与否。这将等同于简单地具有固定上限 √n ，这将给出 O(√n) 的可预测运行时间。

def get_submultiples(n):
    submultiples = set()
    for i in range(1, math.ceil(math.sqrt(n)) + 1):
        if n % i == 0:
            submultiples.add(i)
            submultiples.add(n // i)
    return submultiples

您也可以使用生成器表达式编写它:

def get_submultiples(n):
    return set(itertools.chain.from_iterable(
        (i, n // i)
        for i in range(1, math.ceil(math.sqrt(n)) + 1)
            if n % i == 0
    ))

或者作为生成器:

def get_submultiples(n):
    for i in range(1, math.ceil(math.sqrt(n)) + 1):
        if n % i == 0:
            yield i
            yield n // i