입력 갯수(혹은 크기)에 따른 연산의 수(반복의 수 )를 함수화 시킨 것을 시간 복잡도라고한다. 정의에서 나와있듯 함수의 결과 값이 아닌, 함수 자체를 의미하기 때문에 시간 복잡도는 절대적인 시간을 측정하는 기준이 아니다.
int N = 10;
int ret = 0;
// Case 0
for (int i = 0; i < N; i++)
{
ret += i;
}
// Case 1
for (int i = 0; i < N; i++)
{
// somthing task about I/O;
}
|
예를들어 위와같이 두가지 케이스가 있다고 했을때, 둘의 시간복잡도는 동일하기 N 이지만
일반적으로 입출력(I/O) 작업이 더하기 보다는 느리기 때문에 Case1의 수행시간이 더 오래걸릴 것이다.
시간 복잡도라는 것은 입력 갯수에 따른 시간의 변화율을 알아보기위한 표기법 정도로 받아들이면 좋을 것 같다.
■ 선형 시간
위의 Case0 이 선형시간에 해당한다. 입력갯수에 따라 동일하게 늘어나는 경우를 선형 시간이 걸린다고 한다.
for (int i = 0; i < N; ++i)
{
for (int j = 0; j < 100; ++j)
{
// Something task
}
}
|
예를 들어 이런식으로 반복문안에 매번 100번의 반복문들 돌린다해도 이때도 선형시간이 걸렸다고한다. 왜냐하면 100*N 번의 반복 수행을하는 것이고 이것또한 선형적이기 때문이다.
■ 다항 시간
Colored By Color Scripter™
for (int i = 0; i < N; ++i)
{
for (int j = 0; j < N; ++j)
{
// Something task
}
}
|
위와 같이 N의 m제곱인 형태(여기선 2제곱)을 다항시간이 걸린다고한다. 여기서도 마찬가지로 K*N 이나 N+K 처럼 상수 곱과 더하기는 무시한다.
■ 선형 이하 시간
■ 지수 시간
