python - Python 时间复杂度：For 循环

Question

下面的代码使用嵌套循环list a将 的每个元素与 的所有其他元素相乘list b。我意识到每个循环的时间复杂度是O(n)并且这n是一个相当小的值，但是如果n太大而无法处理怎么办？那就是如果lists a,b值太大了？对于应用的相同功能，我如何更改代码的时间复杂度。

a = [1,2,3]
b = [4,5,6]
new = []
if len(a) == len(b):
     for x in a:   # O(n)
         for y in b:   # O(n)
             new.append((x*y))
print(new)

标签： pythonalgorithmtime-complexity

Answer 1

我看不到改善 O(n^2) 运行时间的方法。n 计算乘法，以便您可以缓存值。这将是相同的复杂性，您的算法会更慢。