通过改变范围来改变时间复杂度

Question

我正在解决 Codility 的 MinPerimeterRectangle 问题：

给定一个整数N，表示某个矩形的面积。

边长为A、B的长方形面积为A * B，周长为2 * (A + B)。

目标是求出任意一个面积为N的矩形的最小周长。这个矩形的边只能是整数。

例如，给定整数N = 30，面积为30的矩形是：

(1, 30)，周长为62， (2, 15)，周长为34， (3, 10)，周长为26， (5, 6)，周长为22。写一个函数：

def 解(N)

给定一个整数 N，returns 是面积正好等于 N 的任何矩形的最小周长。

例如，给定一个整数 N = 30，函数应该 return 22，如上所述。

为以下假设编写一个有效的算法：

N 是 [1..1,000,000,000] 范围内的整数。

我最初使用这个代码：

''' 导入数学

def solution(N):
    a = int(math.sqrt(N))
    for i in range (a,N+1):
        if N % i == 0:
            A = int(i)
            B = int(N/i)
            peri = 2*(A+B)
            return(peri)
    pass

'''

获得总分60%，检测时间复杂度为O(sqrt(N))。然后只需更改第 6 行的范围，时间复杂度就提高到 100%。

''' 导入数学

def solution(N):
    a = int(math.sqrt(N))
    for i in range (a,0,-1):
        if N % i == 0:
            A = int(i)
            B = int(N/i)
            peri = 2*(A+B)
            return(peri)
    pass

'''

我注意到对于第一个，当 N 是一个大素数时会出现超时错误。但是，从数学上讲，我认为这两个范围的长度相等。那为什么不一样呢？

Answer 1

你的问题的答案很简单。我假设您知道当长度等于宽度时周长最小，这意味着如果没有限制 l 和 b 必须是自然数，您可以将面积平方根的两倍作为周长，但是因为你有约束，所以长度和宽度应该尽可能接近。

例如：对于 30 的面积，最小周长在 (5,6)，对于 20，它在 (4,5)，对于 12，它在 (3,4)... ....等等。

将其翻译成书呆子计算机语言将意味着您应该得到以平方根为单位的维度对是迭代次数，即您实现得很好的 O(n^0.5)。现在质数的问题是它们除了一个和它们自己之外没有其他因素......这意味着即使你从面积的平方根开始，你也必须一直迭代直到 n 或所有一直下降到 1。对于大数，迭代回到 1 比迭代到 n 更容易（记住这是 n^0.5 而不是 n/2，因此是扭曲）。为了更好地解释这一点，您可以这样想，从 5 迭代到 1 比从 5 迭代到 25 更容易，从 8 迭代到 1 比从 8 迭代到 64 快 :)。

因此，当您向下而不是向上迭代时，您能够更快地找到最小对。希望这能回答您的问题。

编码愉快！

通过改变范围来改变时间复杂度

Different time complexity just by changing range

time-complexity