| 사례 1 | 사례 2 | 사례 3 | 일반규칙 |

일반 규칙

①
 

규칙 1 (For문) :
     For 순환문의 수행시간은 순환문 내부의 수행시간 반복회수로 계산한다.

②


 

규칙 2 (중복For문) :
     중복된 For 순환문의 수행시간은 안쪽(가장 깊은 곳)에서 바깥쪽으로 중복되는 반복회수를 모두 곱하여 계산한다. 예와 같은 프로그램 수행시간은 O(n²)이다.

  for(i=0; i<n; I++)
            for(j=0; j<n; j++)
                k++;

③

규칙 3 (순차구조문)
     두 그룹의 프로그램이 연속하여 순차적으로 수행될 경우에 수행시간은 그들을 합하여 계산한다. 예와 같이 O(n)의 프로그램과 O(n²)의 프로그램이 연속하여 나올 경우 수행시간은 O(n)+O(n²)=O(n²)이 된다.

  for(i=0; i<n; i++)
           a[i]=0;
       for(i=0; i<n; i++)
           for(j=0; j<n; j++)
               a[i]+=a[j]+i+j;

④

 

규칙 4 (IF/ELSE문)
        if(cond) S1 ELSE S2
     위와 같은 경우 조건의 검사와 S1과 S2중에서 수행시간이 큰 것을 합한 시간으로 계산한다.

⑤
 

 그 외에 함수나 부프로그램의 호출이 있을 때는 그것의 수행시간을 먼저 계산한다. 재귀함수의 경우에는 여러 가지 방법이 있겠지만 for문으로 바꿀 수 있는 경우에는 쉽게 계산할 수 있다.