如何找到以下程序的复杂性？

Question

所以我不是 CS 专业的，很难回答有关程序大 (O) 复杂性的问题。

我编写了以下例程来输出数组中的数字对，其总和为 0：

asd=[-3,-2,-3,2,3,2,4,5,8,-8,9,10,-4]

def sum_zero(asd):
    for i in range(len(asd)):
        for j in range(i,len(asd)):
            if asd[i]+asd[j]==0:
                print asd[i],asd[j]

现在，如果有人问这个方法的复杂性，我知道自从第一个循环遍历所有 n 项以来，它将超过（除非我错了）但是有人可以解释如何找到正确的复杂度？

有没有更好更有效的方法解决这个问题？

Answer 1

我不会给你一个完整的解决方案，但会尽力指导你。

你应该拿一支铅笔和一张纸，然后问问自己：

语句print asd[i], asd[j]执行了多少次？（在最坏的情况下，这意味着你不应该真正关心那里的情况）
你会发现它真的取决于它上面的循环，它被执行 len(asd)（用 n 表示）次。

你唯一需要知道的是，考虑到外循环有 n 次迭代，内循环执行了多少次？（i 从 0 到 n）

如果你还不确定结果，就拿一个真实的例子，比如说n=20，计算最低的语句执行了多少次，这样就可以了给你一个很好的答案指示。

Answer 2

def sum_zero(asd):
    for i in range(len(asd)):       # len called once =  o(1), range called once = o(1)
        for j in range(i,len(asd)): # len called once per i times = O(n), range called once per i times = O(n)
            if asd[i]+asd[j]==0:    # asd[i] called twice per j =  o(2*n²) 
                                    # adding is called once per j =  O(n²)
                                    # comparing with 0 is called once per j = O(n²)
                                        
                print asd[i],asd[j] # asd[i] is called twice per j = O(2*n²)
                
sum_zero(asd) # called once, o(1)

假设最坏的情况（if-condition 始终为真）：

Total:
O(1) * 3
O(n) * 2
O(n²) * 6

O(6n² + 2n + 3)

演示复杂性的简单程序：

target= []
quadraditc = []
linear = []
for x in xrange(1,100):
    linear.append(x)
    target.append(6*(x**2) + 2*x + 3)
    quadraditc.append(x**2)

import matplotlib.pyplot as plt
plt.plot(linear,label="Linear")
plt.plot(target,label="Target Function")
plt.plot(quadraditc,label="Quadratic")
plt.ylabel('Complexity')
plt.xlabel('Time')
plt.legend(loc=2)
plt.show()

编辑：

正如@Micah Smith 所指出的，上面的答案是最坏情况操作，Big-O 实际上是 O(n^2 )，因为省略了常量和低阶项。

如何找到以下程序的复杂性？

How to find complexity for the following program?

python

big-o

code-complexity

编辑：