[1주차] 알고리즘의 성능 분석 - 시간 복잡도

 

멋쟁이사자처럼 프론트엔드 부트캠프 플러스 5기는 무사히 수료하였지만, 같은 기수 동기들과 함께 알고리즘 스터디를 꾸렸다.

각자의 개인 학습 정리를 리뷰하는 시간이 모임에 존재하기 때문에 그 첫 정리는 알고리즘, 코딩테스트에 가장 기초적인 지식, 알고리즘의 성능 분석에 대한 학습을 마쳐 정리를 해보고자 한다.

 

---

 

📈 이건 알고 가자, 지수함수와 로그함수의 그래프

 

알고리즘의 성능 분석에 대해 알아가기 전에 기초적으로 알아가야할 간단한 수학적 지식이라고 한다면 지수 함수와 로그 함수의 그래프에 있을 것 같다. big-O 표기법으로 시간복잡도를 나타낸다고 했을 때, 지수와 로그는 필연적으로 등장하기 때문이다.

 

지피띠니가 만들어줘써요

 

파란색의 경우 지수 함수의 그래프,

$$y = 2^{x}$$

빨간 색의 경우에는 로그 함수의 그래프이다. 

$$y = \log_{2} x$$

 

정확히 두 함수의 계산을 이해하는 것보다도, 그래프의 형상 자체를 기억하는 것만으로도 도움이 된다.

빅 오 표기법에서 n이 지수 함수이거나 로그 함수인 경우의 시간 복잡도의 증가 형상을 쉽게 이해할 수 있기 때문이다.

 

 

⏰ 시간 복잡도 (Time Complexity)

 

💡"어떤 알고리즘이 어떠한 상황에서 더 빠르고 또 느리냐?" - 윤성우의 열혈 자료구조 중

 

공간 복잡도 (Space Complexity)에 대해서는 이 포스팅에서 다루지는 않겠다.

(어떠한 상황에서 메모리 등의 하드웨어 용량을 얼마나 차지하는지에 대한 시간복잡도이다.)

 

 

시간 복잡도의 유형

 

시간 복잡도를 정의하는 유형에는 아래의 세 가지가 있다.

• 빅-오메가 표기법 : best case의 연산 횟수를 나타내는 표기법
• 빅-세타 표기법 : average case의 연산 횟수를 나타내는 표기법
• 빅-오 표기법 : worst case의 연산 횟수를 나타내는 표기법

 

대표적인 시간복잡도 표기법 Big-O

 

우리는 이 중에서 빅-오 표기법 (O(n))을 기준으로 수행 시간을 계산하는 방법을 사용한다.

다양한 테스트 케이스를 수행하여 모든 케이스를 통과해야만 하기 때문이기에 최악인 경우를 염두에 두고 문제에 접근해야하기 때문이다.

 

 

시간 복잡도의 연산 횟수 계산 방법

 

C++의 경우, 1억 번의 연산을 1초의 수행 시간으로 예측할 수 있다고 한다.

연산 횟수를 계산할 때에는 시간 복잡도의 n 값에 데이터의 크기를 대입하여 도출할 수 있다.

 

만약 N개의 수를 오름차순으로 정렬해야 하는 문제를 2초 안에 해결해야 한다고 가정해보자.

그렇다면 연산 횟수는 2억 번의 연산 이내로 끝내야 한다.

 

$$1 \leq N \leq 1,000,000$$

이 때 N의 범위는 위와 같다.

 

시간 복잡도가 아래와 같은 버블 정렬과

$$O(n^{2})$$

아래와 같은 병합 정렬 중

$$O(\n log n)$$

 

버블 정렬을 이용할 경우 (1,000,000) ^ 2 = 1,000,000,000,000 > 200,000,000 이므로 적합하지 않은 알고리즘이고

병합 정렬을 이용할 경우 1,000,000 log (1,000,000) = 약 20,000,000 < 200,000,000 이므로 적합한 알고리즘이다.

 

이런 방법으로 문제 풀이에 적합한 알고리즘을 파악해낼 수 있는 것이다.

 

 

시간 복잡도 도출 기준

 

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

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

 

상수는 시간 복잡도 계산에서 제외한다?

• 코딩 테스트에서는 일반적으로 상수를 무시한다.
• 시간 복잡도가 O(2n) 이라면 상수는 시간 복잡도 계산에서 제외하므로 O(n)과 동일하다.
• 중첩되지 않은 반복문의 갯수가 3개라면 해당 시간 복잡도는 O(3n) -> O(n)

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

• 시간 복잡도는 가장 많이 중첩된 반복문을 기준으로 도출한다.
• 이중 중첩 for문의 경우 O(n^2), 반복문의 중첩 횟수에 따라 시간복잡도는 지수로 증가한다.

 

 

---

 

😇 마치며

 

이렇게 스터디에서 필요한 수준으로의 시간 복잡도 개념을 정리해보았다.

대학교 강의나 혼자서 알고리즘 문제 풀이를 공부하며 지겹도록 본 개념이라 다시 한 번 짚어간다는 느낌으로 가져갔다.

스터디를 주최한 것이 나인 만큼, 성실하게 스터디에 임하고 싶다...