시간 복잡도란 입력 크기에 대해 알고리즘이 실행되는데 걸리는 시간이며 주요 로직의 반복 횟수를 중점으로 측정됩니다. 컴퓨터마다 사양이 다르기 때문에 시간으로만 성능을 표현하기가 애매할 수 있습니다. 그렇기 떄문에 시간 복잡도는 알고리즘의 성능을 표현할 때 유용합니다. 하지만, 시간 복잡도 또한 알고리즘의 성능을 완벽하게 표현할 수 없기 때문에 직접적으로 알고리즘 수행 시간이 얼마나 소요되는지 테스트 하는 것이 좋을 때도 있습니다.
Big-O 표기법( Big-O notation )
Big-O 표기법( Bit-O notation )이란 복잡도에 가장 영향을 많이 끼치는 항의 상수 인자를 빼고 나머지 항을 없애서 복잡도를 나타내는 표기법입니다.
Big-O 표기법 예시
for(int i = 0; i < 10; ++i){
for(int j = 0; j < n; ++j){
for(int k = 0; k < n; ++k){
std::cout << i << j << k;
}
}
}
위 코드의 시간 복잡도는 10n^2 + n 입니다. 해당 시간 복잡도를 Big-O 표기법으로 순서대로 바꾼다면 가장 영향을 많이 끼치는 항의 상수를 제거하였을 때 n^2 + n 이고 나머지 항을 제거한다면 n^2 입니다. 즉, 위 코드는 Big(n^2)으로 표현할 수 있습니다.
가장 많이 영향을 끼치는 항이란 입력값이 커짐에 따라 소요시간이 가파르게 증가하는 항을 말합니다.
