Big O 표기법은 어떻게 작동합니까?

Question

그래, 코드 작성에 상당히 익숙하다. WCET T (a, b)와 함수의 복잡성을 근사화하려고한다. 예 기능 :이 기능의 복잡성이 차 O (N^2)하지만 난이 WCET를 근사에 확실하지 않다 이해

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

?

또한되고, 그 기능이 단지 두 할당 아니다 :

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 

위한 참고 것 A = NB = N 다음 말할 수 O (N^2) 경우 항상 testFunction2 True를 반환이 함수

WCET B는 x = x +1는 B 번 실행할 수 있지만 못해 실행 시간의 합 영향. N = 1000과는 = B = N

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

이 결과를 evalute 때 그래서 2002을 볼 수 당신 동안 아무것도 동안, 예를 들어

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

: 은 마지막으로이 모든 exection 시간 합계

Answer 2

최악의 경우 실행 시간은 프로그램을 느리게 만들 수 있도록 특별히 고안된 입력이 있다고 가정 할 수 있습니다. 이 경우 testfunction2는 항상 true를 리턴합니다.

루프 본문 내에서 x = x + 1은 최악의 경우 a * b 번 발생합니다.

대신 (N^2) O로 이렇게 설명하는, I는 O (AB)으로 설명하고,이어서 ~ = B ~ = O 인 N (N^2)