|
|
간단한 수행시간 계산 (사례 1)
|
|
■ 다음 프로그램은 을 구하는 프로그램
|
int sum( int n )
{ int partial_sum
= 0; ································· ①
for(
int i = 1; i <= n; i++ ) ······················
②
partial_sum += i * i * i;
························
③
return
partial_sum; ································
④
}
|
1단위
2n+2 단위
3n 단위
1단위
|
이 프로그램은 ①행, ④행에서 각각
1단위, ③행에서 3n 단위, ②행에서 2n+2 단위 시간이 수행되며
따라서 총 5n+4단위시간이 걸린다. 즉, 이 프로그램의 수행시간은 O(n)
이다.
이와 같은 계산을 빠르게 추정하는 방법은 중요하지
않은 곳은 생략하고 상수도 생략하면서 계산하는 방법이다.
즉, 3행의 수행시간은 O(1)이며, for문이 n번 반복되므로 O(n)이라고
빨리 계산할 수 있다.
|
