https://yoongrammer.tistory.com/79
시간 복잡도
알고리즘의 수행 시간을 분석할 때 시간 복잡도를 사용합니다.
수행 시간은 실행환경에 따라 다르게 측정되기 때문에 기본 연산의 실행 횟수로 수행 시간을 평가합니다.
기본 연산은 다음과 같습니다.
시간 복잡도는 3가지 경우로 나타냅니다.
평균적인 경우를 가장 많이 사용할 것 같지만 알고리즘이 복잡해질수록 평균적인 경우는 구하기가 매우 어려워 지기 때문에 최악의 경우로 알고리즘의 성능을 파악합니다.
시간 복잡도는 일반적으로 빅오 표기법으로 나타냅니다.
연산 횟수가 다항식으로 표현될 경우, 최고차항을 제외한 모든 항과 최고차항의 계수를 제외시켜 나타냅니다.
int func (int n) {
int sum = 0; // 대입연산 1회
int i = 0; // 대입연산 1회
for(i=0; i < n; i++) { // 반복문 n+1회
sum += i; // 덧셈 연산 n회
}
for(i=0; i < n; i++) { // 반복문 n+1회
sum += i; // 덧셈 연산 n회
}
return sum; // 리턴 1회
}
T(n) = 4n + 5 = O(n)
입력 크기(n)에 상관없이 일정한 연산을 수행하면 시간복잡도는 O(1)입니다.
void func (int n) {
printf("%d\n", n);
}
T(n) = O(1)