时间戳

首页 > 解决方案 > 如何降低给定 python 代码的时间复杂度？

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

问题描述

我有这个 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 循环，以便以更小的时间复杂度执行程序？

标签： python-3.xtime-complexity

解决方案

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

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

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

第 1 节 - 变量声明和输入

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

您可以轻松地省略完美正方形、count 和 total_length 的声明，因为它们不是必需的，如进一步解释的那样。这将降低代码的时间和空间复杂性。

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

第 2 部分 - 查找所有因素

for i in range(1, number):
    if number%i == 0:
        factors.append(i)
  1. 在这里，您可以使用列表推导技术来创建因子列表，因为列表推导比循环语句更快。
  2. 此外，您可以只迭代直到 Number 的平方根，而不是循环直到 number 本身，从而以指数方式降低时间复杂度。上面的代码部分枪到...
应用 '1' hack 后

因子 = [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)))

推荐阅读