알고리즘 - 시간복잡도

 

시간복잡도는 컴퓨터 프로그램이나 알고리즘이 일을 얼마나 빠르게 처리하는지를 나타내는 중요한 개념이다. 이는 주로 알고리즘의 연산 횟수와 관련이 있다는데, 연산 횟수가 적을수록 알고리즘은 빠르고 효율적이라고 할 수 있다.

 

 

시간복잡도는 다음과 같은 이유로 알고리즘을 공부할때 기본적으로 필요하다.

1. 효율성 평가: 우리가 만든 프로그램이 얼마나 빠르게 동작하는지 확인할 수 있다. 우리가 진행하는 코딩테스터에서 제일 막히는 부분이 '시간제한'인 만큼, 시간복잡도를 통해 더 효율적인 알고리즘을 선택하거나 개발할 수 있다.

 

2. 자원 절약: 시간복잡도를 고려하면 컴퓨터의 자원을 효율적으로 사용할 수 있다. (더 빠른 알고리즘은 더 적은 시간과 메모리를 사용하니까.)

3. 문제 해결 능력 강화: 시간복잡도를 고려하면 어떤 문제를 해결할 때 논리적으로 생각하게 되고, 더 효율적인 방법을 찾게 된다. 이것은 프로그래밍 뿐만 아니라 일상적인 문제해결 능력에도 도움이 된다.

 

 

시간 복잡도 기호

빅오 표기법 (Big-O Notation)

빅오 표기법은 알고리즘의 최악의 실행 시간을 표현하는 표기법. O( ) 안에 함수를 넣어서 표현한다.
예를 들어, O(n)은 선형 탐색과 같이 입력 크기에 비례하는 알고리즘을 나타낸다.

오메가 표기법 (Omega Notation)

오메가 표기법은 알고리즘의 최상의 실행 시간을 표현하는 표기법. Ω( ) 안에 함수를 넣어서 표현한다.
예를 들어, Ω(1)은 상수 시간이 걸리는 알고리즘을 나타낸다.

 

시간복잡도의 사용 예시

1. 선형 탐색과 이진 탐색:
   - 선형 탐색: 하나씩 차례로 확인하는 방법. 만약 우리가 책장에서 책을 찾는다고 생각보자. 한 권씩 확인하면서 찾는 것이 선형 탐색이다. 시간복잡도는 O(n)이다.
   - 이진 탐색: 정렬된 상태에서 중간값을 확인하고 찾고자 하는 값이 왼쪽에 있으면 왼쪽 반을, 오른쪽에 있으면 오른쪽 반을 탐색하는 방법. 시간복잡도는 O(log n)이다.
   ex) 100권의 책 중에서 특정한 책을 찾는다고 생각해보자. 선형 탐색은 한 권 한 권 찾아야 해서 더 많은 시간이 걸리지만, 이진 탐색은 중간값을 확인하면서 빠르게 찾을 수 있다.

2. 버블 정렬과 퀵 정렬
   - 버블 정렬: 인접한 두 원소를 비교하면서 정렬하는 방법. 시간복잡도는 O(n^2)이다.
   - 퀵 정렬: 피벗(pivot)을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 나누어 정렬하는 방법. 시간복잡도는 O(n log n)이다.
   ex) 10개의 숫자를 정렬한다고 생각해보자. 버블 정렬은 인접한 숫자를 비교하면서 정렬하기 때문에 시간이 오래 걸리지만, 퀵 정렬은 피벗을 기준으로 나누어 빠르게 정렬할 수 있다.

3. 재귀 함수의 시간복잡도
   - 재귀 함수는 자기 자신을 호출하는 함수이다. 이때 중요한 것이 재귀 호출의 깊이와 각 호출이 얼마나 많은 작업을 하는지에 따라 시간복잡도가 결정된다.
   ex) 피보나치 수열을 계산하는 프로그램을 만든다고 생각해보자. 각 재귀 호출마다 두 번의 재귀 호출이 일어나므로 시간복잡도는 O(2^n)이다. 반면에 동적 계획법을 사용하면 시간복잡도를 획기적으로 줄일 수 있다.



이렇듯 시간복잡도는 우리가 프로그램을 작성할 때 고려해야 하는 중요한 요소이다. 효율적인 알고리즘을 선택하고 개발하면 프로그램이 빠르고 효율적으로 동작할 수 있다. 또한, 시간복잡도를 고려하면 문제를 더 논리적으로 해결하는 습관을 기를 수 있어, 프로그래밍 뿐만 아니라 여러 분야에서 이 개념을 활용할 수 있으니 잘 기억해두어야한다. (제발 체화하자)