大O符号是怎么工作的？

Question

好吧，我对编码还比较陌生，我要近似一个WCET T（a，b）和一个函数的复杂度。示例函数：

def testFunction(self):
    x = 0
    for r in range(a):
        for c in range(b):
            if testFunction2(r, c):
                x = x + 1
return x

我知道这个函数的复杂度是二次的O（N^2），但我不确定如何逼近WCET？你知道吗

在这个函数中不是只有两个赋值吗

x = 0

以及

x = x + 1

什么？ 如果是的话，我如何用T（a，b）表示赋值？你知道吗

数学从来不是我的强项，但我想学怎么做。我读过的材料中没有一个能以我理解的方式解释它。你知道吗

提前谢谢。你知道吗

Answer 1

def testFunction(self):
    x = 0                               # 1
    for r in range(a):                  # a
        for c in range(b):              # b
            if testFunction2(r, c):     # a*b
                x = x + 1               # depends testFunction2
    return x                            # 1

对于这个函数ab，其中a=nb=n，那么你可以说O（n^2） 如果总是testFunction2返回True，那么x = x +1将执行ab次，但不会影响执行时间的总和。 最后你把所有的执行时间加起来：

(1 + a + b + a*b + a*b + 1)
2 + a + b + 2*a*b

例如，当n=1000和a=b=n

2 + 1000 + 1000 + 2*1000*1000
2002 + 2000000

所以当你评估这个结果的时候，你会发现2002年什么都不是，而你有2000000。你知道吗

Answer 2

对于最坏情况下的执行时间，您可以简单地假设有一个专门设计的输入使您的程序变慢。在这种情况下，testfunction2总是返回true。你知道吗

在循环体中，赋值x = x + 1在最坏的情况下发生a * b次。你知道吗

我不把它描述为O（N^2），而是把它描述为O（ab），然后注意a~=b~=N就是O（N^2）