예를 들어 입력 데이터 수가 64로 적은 경우에도 연산 횟수가 표 아래로 향할수록 기하급수적으로 늘어나는 것을 확인할 수 있습니다. 만약 문제에서 주어진 입력 데이터 수가 10만 개고, 사용하는 알고리즘의 시간 복잡도가 O(n²)이라면 10만 x 10만으로 100억 번 연산을 수행하게 됩니다. 컴퓨터는 대략 1초에 1억 번(왜 1억 번인지는 잠시 뒤에 알아볼게요) 연산하므로 이 프로그램은 동작하는 데 100초가 걸린다는 결론을 낼 수 있습니다.

따라서 시간 복잡도가 어떨지 미리 생각하고, 문제가 생길 여지가 있으면 이를 개선하는 습관을 들여야 합니다. 예를 들어 문제에서 주어진 ‘입력값의 최대 크기가 10만 개라면 시간 복잡도가 O(nlogn) 정도인 알고리즘으로 문제를 풀어야 한다’는 것을 알고 그에 맞는 알고리즘을 선택해야 합니다. 만약 O(nlogn)이 아닌 O(n²) 시간 복잡도인 알고리즘으로 풀면 높은 확률로 시간 초과가 발생해 테스트에 실패합니다.

각 시간 복잡도의 개념과 사용되는 상황 등을 좀 더 자세하게 알아보겠습니다.

• O(1): 입력 데이터 수의 크기와 복잡도에 상관없이 항상 상수(고정된 시간)를 가지는 알고리즘입니다. 예를 들어 ‘내림차순으로 정렬된 숫자 배열에서 제일 큰 수를 알아내는 함수’가 있다면 제일 큰 숫자는 배열의 가장 마지막 요소이므로 이를 불러오기만 하면 됩니다. 즉, 연산은 1번이면 충분합니다. 이 알고리즘은 전체 시간 복잡도를 계산할 때 연산 횟수에 거의 영향을 받지 않습니다. 해시 테이블의 삽입, 삭제, 검색 시에도 상수 시간을 보장합니다.