为什么我的python代码的时间复杂度为O（N ** 2）[关闭]

Question

我很难理解如何计算python代码的时间复杂度。为什么下面的代码O（N ** 2）的时间复杂度？

from itertools import permutations

indices = list(permutations(range(len(A)),2))
indices = list(filter(lambda x: x[0] < x[1], indices))
Y = [(A[i], A[j]) for i,j in indices]

count = sum(x>y for x,y in Y)

if count >= 1000000000:
    count = -1
return count

Answer 1

你有一个列表（或其他可索引对象A），并试图计算有多少对A[i]，A[j]（其中i <j）有A[i] > A[j]。

你当前的实现需要考虑所有对i，j，并且它们有O（len(A)**2）。 （因此你有O（n**2）比较。）

您可以通过创建元组(A[i], i)并对它们进行排序（在A[i]上）来做得更好。然后一些聪明的计数算法，当索引失序（和多少）时，可能会给你结果。排序将是O（n ln n），对索引的扫描甚至可能是线性的。

排序看起来像：

import operator
sortedA = sorted( enumerate(A), operator.itemgetter(1) ) // Sort by A[i]

扫描看起来像：

count = 0
for x in sortedA:
    finalPosition = x[0]
    originalPosition = x[1][0]
    // I am almost certain the next two lines are wrong - but something
    // similar ought to do the job
    if finalPosition < originalPosition:  
        count += originalPosition - finalPosition

---

您可以通过不创建列表来加速当前代码。

indices = permutations(range(len(A)),2)
indices = filter(lambda x: x[0] < x[1], indices)
count = sum(A[i] > A[j] for i,j in indices)

（但这不如O（n**2）到O（n log n）那么好