algorithm - 有人可以向我解释为什么完美平方的运行时间是 O(sqrt(n)) 吗？

Question

Problem

• 给定一个正整数 n，找到最少数量的完全平方数(例如 1、4、9、16...)，其总和为 n。

  示例 1: 输入:n = 12 输出:3 解释:12 = 4 + 4 + 4

  示例 2: 输入:n = 13 输出:2 解释:13 = 4 + 9。

Suggested Solution (BFS)

def numSquares(self, n):
    if n < 2:
        return n
    lst = []
    i = 1
    while i * i <= n:
        lst.append( i * i )
        i += 1
    cnt = 0
    toCheck = {n}
    while toCheck:
        cnt += 1
        temp = set()
        for x in toCheck:
            for y in lst:
                if x == y:
                    return cnt
                if x < y:
                    break
                temp.add(x-y)
        toCheck = temp

    return cnt

这个特定的 BFS 如何在 O(sqrt(n)) 中运行？因为我的想法是找到平方需要 O(sqrt(n))。因为有 2 个 for 循环，(for y in lst1 需要 O(sqrt(n))，for x in toCheck 需要 O(sqrt(n))，应该'是 O(n) 吗？？

Answer 1

运行时间实际上是Theta(n^(3/2))。根据Legendre's three-square theorem ，对于整数 a 和 b 来说，任何形式为 4^a (8b + 7) 的整数都可以写成四个平方和，但是不是三个。令n 为此类整数。有小于 n 的 Omega(n) 数字可以写成三个平方和，因此在 while 循环的最后一次迭代中，toCheck 具有 Theta(n) 元素，lst 具有 Theta(n^(1/2))。