시간복잡도 정리

알고리즘에서 시간복잡도는 주어진 문제를 해결하기 위한 연산 횟수를 말합니다. 

일반적으로 수행시간은 1억번의 연산을 1초의 시간으로 간주하여 예측 합니다.

ex) 시간제한이 2초면 약 2억번의 연산 안에 해결해야 된다는 뜻

 

시간 복잡도 유형

 

1. 빅-오 : 최악일때의 연산 횟수를 나타낸 표기법

2. 빅-세타 : 보통(평균)일때의 연산 횟수를 나타낸 표기법

3. 빅-오메가 : 최선일때의 연산 횟수를 나타낸 표기법

 

코딩테스트에서는 다양한 테스트 케이스를 수행해 모든 케이스를 통과해야만 합격이기 때문에 빅-오 표기법( O(n) ) 기준으로 수행시간을 계산하는 것이 좋습니다.

 

 

 

알고리즘별 시간복잡도를 예를 들어보자면 버블정렬 O(n^2), 병합정렬 O(nlog n), 바이너리 서치 O(log n).

 

 

연산 횟수 계산 방법

 

연산 횟수 = 알고리즘 시간 복잡도 x 데이터의 크기

 

 

아래에서 문제를 통해 시간 복잡도를 알아보겠습니다.

 

 

---

 

문제

N개의 수가 주어졌을때 이를 오름차순 정렬하는 프로그램을 작성하시오. (제한시간 2초)

 

입력

 

1번째 줄에 수의 개수 N(1 <=  N <= 1,000,000), 2번째 줄부터는 N개의 줄에 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

 

출력

 

1번째 줄부터 N개의 줄에 오름차순 정렬한 결과를 1줄에 1개씩 출력한다.

 

입력 1	출력 1
5 5 2 3 4 1	1 2 3 4 5

 

 

풀이

 

시간제한이 2초 이므로 이 조건을 만족하려면 2억번 이하의 연산 횟수로 문제를 해결해야 합니다.

※ 시간 복잡도는 항상 최악일때, 즉 데이터의 크기가 가장 클때를 기준으로 합니다.

 

연산 횟수 = 알고리즘 시간 복잡도 x 데이터의 크기

위 공식을 대입해 어떤 알고리즘이 이문제에 적합한지 판단해 보겠습니다.

 

알고리즘 적합성 평가

버블 정렬 = (N)^2 = (1,000,000)^2 = 1,000,000,000,000 결과는 2억번 연산횟수를 초과함 (부적합 알고리즘)

병합 정렬 = n log n = 1,000,000 log(1,000,000) = 약 2,000,000 ( log1,000,000은 약 20) 결과가 2억번 연산횟수 보다 작음 (적합 알고리즘)

 

 

시간복잡도 도출 방법

1. 상수는 시간복잡도 계산에서 제외합니다.

2. 가장 많이 중첩된 반복문의 수행횟수가 시간 복잡도의 기준이 됩니다.

 

 

연산 횟수가 N인 경우

위의 경우는 연산 횟수가 N인 경우로 시간복잡도 O(N)일 경우 입니다.

int N = 100000번일때 반복문으로 N번 만큼 반복 하기 때문에 데이터 크기만큼 연산횟수가 발생 하기 때문에 O(N)입니다. 

 

 

연상 횟수가 3N인 경우

위의 경우는 100000번의 크기의 반복문을 3번 돌리는 경우로 O(3N)인 경우 입니다. 하지만 코딩에서 N이나 3N이나 결과 적으로 걸리는 시간이 큰 차이가 없기 때문에 시간복잡도에서의 상수는 무시할수 있습니다. 결국 시간복잡도는 O(N)과 같습니다.

 

 

연산횟수가 N^2인 경우

시간복잡도는 가장 많이 중첩된 반복문을 기준으로 도출하므로 이 코드에서는 이중 for문 O(N^2)이 전체코드의 시간복잡도 기준이 됩니다. 만약 일반 for문의 10개가 더 있더라도 도출 원리의 기준에 따라 시간복잡도는 변함없이 N^2가 됩니다.

 

이와 같이 자신이 작성한 코드의 시간 복잡도를 도출할수 있다면 실제 코딩 테스트에서 시간초과가 발생 했을때 이 원리를 바탕으로 문제가 되는 부분을 도출할수 있고 더욱 효율적인 구조로 수정하는 작업으로 문제를 해결할수 있습니다.

 

---

 

출처 

https://www.inflearn.com/course/lecture?courseSlug=%EB%91%90%EC%9E%87-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%EC%9E%90%EB%B0%94&unitId=148247&tab=curriculum

학습 페이지