如何降低给定 python 代码的时间复杂度？

Question

我有这个 python 程序，它计算给定数字的“自由平方数”。我面临着时间复杂度的问题，即我在在线编译器中收到“超出时间限制”的错误。

number = int(input())
factors = []
perfectSquares = []
count = 0
total_len = 0

# Find All the Factors of the given number
for i in range(1, number):
if number%i == 0:
    factors.append(i)

# Find total number of factors        
total_len = len(factors)

for items in factors:
    for i in range(1,total_len):
  # Eleminate perfect square numbers
    if items == i * i:
        if items == 1:
            factors.remove(items)
            count += 1
        else:
            perfectSquares.append(items)
            factors.remove(items)
            count += 1

# Eleminate factors that are divisible by the perfect squares 
for i in factors:
    for j in perfectSquares:
    if i%j == 0:
        count +=1

# Print Total Square Free numbers
total_len -= count 
print(total_len)

如何降低该程序的时间复杂度？那我怎样才能减少for循环，从而使程序以更小的时间复杂度执行呢？

Answer 1

降低 Python 代码时间复杂度 (TC) 的算法技术。

为了降低代码的时间复杂度，无论何时何地减少循环的使用是非常有必要的。

我会将代码的逻辑部分分为 5 个部分，并建议对每个部分进行优化。

第 1 节 - 变量声明和输入

number = int(input())
factors = []
perfectSquares = []
count = 0
total_len = 0

您可以轻松省略完全平方数、计数和总长度的声明，因为不需要它们，如进一步解释的那样。这将降低代码的时间和空间复杂性。

另外，您可以使用快速 IO，以加快输入和输出速度，这是通过使用“stdin.readline”和“stdout.write”来完成的。

第 2 部分 - 查找所有因素

for i in range(1, number):
    if number%i == 0:
        factors.append(i)

1. 在这里，您可以使用列表理解技术来创建因子列表，因为列表理解比循环语句更快。
2. 此外，您可以迭代直到数字的平方根，而不是循环直到数字本身，从而以指数方式降低时间复杂度。上面的代码部分枪械到...

应用“1”黑客后

factors = [for i in range(1, number) if number%i == 0]

应用 '2' hack 之后 - 使用 from_iterable 在列表理解的每次迭代中存储超过 1 个值

factors = list( chain.from_iterable(
  (i, int(number/i)) for i in range(2, int(number**0.5)+1)
    if number%i == 0
  ))

第 3 节 - 消除完全平方数

# Find total number of factors        
total_len = len(factors)

for items in factors:
    for i in range(1,total_len):
  # Eleminate perfect square numbers
    if items == i * i:
        if items == 1:
            factors.remove(items)
            count += 1
        else:
            perfectSquares.append(items)
            factors.remove(items)
            count += 1

实际上你可以完全省略这一部分，只需在第 2 节中添加额外的条件，即 ... type(i**0.5) != int，以消除那些具有整数平方根的数字，因此它们本身就是完美的平方。执行如下......

factors = list( chain.from_iterable(
  (i, int(number/i)) for i in range(2, int(number**0.5)+1)
    if number%i == 0 and type(i**0.5) != int
  ))

第 4 节 - 我认为不需要此节，因为 Square Free Numbers 没有这样的限制

第 5 部分 - 完成计数、打印计数

绝对不需要计数器，您只需计算因子列表的长度，并将其用作计数即可。

优化代码

方式 1 - 快一点

number = int(input())

# Find Factors of the given number
factors = []
for i in range(2, int(number**0.5)+1):
    if number%i == 0 and type(i**0.5) != int:
        factors.extend([i, int(number/i)])

print([1] + factors)

方式 2 - 最佳编程 - 非常快

from itertools import chain 
from sys import stdin, stdout

number = int(stdin.readline())
factors = list( chain.from_iterable(
  (i, int(number/i)) for i in range(2, int(number**0.5)+1)
    if number%i == 0 and type(i**0.5) != int
  ))

stdout.write(', '.join(map(str, [1] + factors)))