[알고리즘] 시간복잡도

SOL·2023년 6월 28일

목록 보기

2/31

1. 개념

코딩테스트에서는 `빅-오` 표기법을 사용합니다. 입력 데이터 중 가장 최악의 상황을 포함한 시간의 상한선을 구합니다.

예시 문제를 풀어보며 시간복잡도 활용방법에 대해 알아보겠습니다.

Q. 문자열의 알파벳 구성을 파악하는 코드의 시간복잡도는?

for (int i = 0; i <str.length(); i++){
	int alphabetIndex = str.charAt(i) - 'A'; // 아스키코드 구하기
    count[alphabetIndex]++;
}

반복문이 시작할때 int i=0 으로 초기화하는 연산. 딱 한번만 실행하므로 +1
반복문의 조건문 i < str.length(). 반복문이 시작하고 끝날때까지 매번 실행됩니다. 반복문이 끝날때에도 조건이 한번 더 실행되고 false가 떨어져야 끝납니다. str.length() 보다 한번 더 실행되므로 +(L+1)
반목문의 증감식 i++. 조건에 맞는 반복문이 끝날때마다 연산됩니다. +L
반복문 내의 로직. 한 라인마다 하나의 연산이라고 가정하면 +(2*L)

총 연산의 횟수는 4*L +2로 입력된 문자열의 길이에 4배만큼 비례합니다.
표기법으로 나타내면 O(4*L+2)인데 우리는 데이터의 크기의 비례한 연산 횟수만을 알고싶기 때문에 모든 상수는 전부 생략해줍니다.

따라서 이 문제의 시간복잡도는 O(L) 입니다. 이 표기법의 의미는 입력된 데이터의 길이에 비례하는 수행시간을 가진 알고리즘 이라고 볼 수 있습니다.

알고리즘 수행이 입력된 데이터(N)에 비례해 선형적으로 증가합니다. 반복문을 기반으로 배열의 모든 원소를 순차탐색하는 형태를 선형 탐색이라고 하며, 선형 탐색의 시간복잡도가 O(N)으로 자주 나타납니다.

이제 선형탐색안에서 다른형태의 탐색이 진행되는 예시문제를 보겠습니다.

Q. 이중반복문의 시간복잡도는?

long sum = 0 ;
for(int i = 0; i < N; i++){
	for(int j = 0; j < M; j++){
    	sum += (long)a[i] * b[j]; // 이연산은 M*N번 반복된다.
    }
}

전체 시간복잡도는 O(M*N)이 됩니다.

코딩테스트에는 문제마다 시간제한이 있습니다.
최악의 테스트 케이스에서도 프로그램이 답을 구할 수 있어야하며, 시간제한 내에 프로그램이 종료되지 않으면 시간초과를 받습니다.
문제를 풀기 전 적합한 알고리즘을 선택하는 기준이 되어줍니다.
그러나 상수/최적화, 언어의 성능, 하드웨어 성능 등에 따라 시간복잡도가 1천만밖에 되지 않아도 1초를 넘기거나, 10억이 넘어도 1초안에 실행될 수도 있습니다. 즉 절대적 지표가 아닌 상대적 지표입니다.
정답을 구하는 알고리즘이 여러개라면 시간 제한에 따라 구현이 쉬운방법을 선택하거나 시간/메모리상으로 효율적인 방법을 택할 수 있습니다.

정렬된 배열에서 특정 원소의 위치를 찾는 문제를 생각해볼때, 배열의 모든 원소를 순회한다면 O(N) 시간 복잡도가 소요됩니다. 하지만 배열을 정렬한다면 이진탐색을 적용하여 O(logN)으로 줄일 수 있습니다.

따라서 문제 조건에 맞는 적절한 자료구조와 알고리즘을 이용하는 것이 시간 복잡도를 줄일 수 있는 핵심입니다.

문제를 보고 효율적인 알고리즘을 바로 떠올리기 어렵다면 문제에서 주어진 입력 조건을 이용하여 시간 복잡도를 유추해 볼 수도 있습니다. 아래 표는 제한시간 1초일때 입력조건에 맞는 유추 가능한 알고리즘입니다.

무조건 해당 입력 조건에 해당 알고리즘을 사용하라는 것은 아니며, 어디까지나 힌트로 사용하면 좋습니다. 항상 시간 복잡도를 따지고 효율성이 검증되면 그때 문제를 푸는 습관을 들이는게 좋습니다.

개발 개념 정리