大 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) 表达赋值？

数学从来都不是我的强项，但我想学习如何做到这一点。 None 我读过的材料以我理解的方式解释了它。

提前致谢。

Answer 1

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

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

与其将其描述为 O(N^2)，不如将其描述为 O(ab)，然后注意 a ~= b ~= N 即 O(N^2)

Answer 2

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

WCET 对于这个函数 ab 其中 a=n b=n 然后你可以说 O(n^2) 如果总是 testFunction2 returns 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。

大 O 符号是如何工作的？

How does Big O notation work?

python

big-o

function

time-complexity