1

所以我不是 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项目，它将超过（除非我错了），但有人可以解释如何找到正确的复杂性吗？

如果有更好更有效的方法来解决这个问题？

4

2 回答 2

3

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

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

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

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

如果您仍然不确定结果，只需举一个真实的例子，例如n=20，计算最低语句执行了多少次，这将为您提供一个很好的答案指示。

于 2015-01-04T22:04:25.363 回答
1 
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)，因为省略了常量和低阶项。

于 2015-01-05T18:15:27.237 回答