Как работает нотация Big 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 

WCET для этой функции а Ь, где а = пь = п, то можно сказать, O (N^2) если всегда testFunction2 возвращает True Then x = x +1 будет выполнять раз б, но оно не влияет на сумму времени выполнения. Наконец вы суммировать все это время exection:

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

, например, в то время как п = 1000 и а = Ь = п

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

поэтому, когда вы вычисляться этот результат вы увидите, 2002 ничего пока вы имеют 2000000.

Answer 2

Для наихудшего случая исполнения, вы можете просто предположить, что есть вход, созданный специально для медленной работы вашей программы. В этом случае функция testfunction2 всегда возвращает true.

В корпусе петли присваивается x = x + 1a * b раз в худшем случае.

Вместо описания это как O (N^2), я бы описал его как O (AB), а затем отметить для ~ = Ь ~ = Н, что это O (N^2)