시간 복잡도란 대체 무엇인가

요즘 코딩테스트 공부를 하면서 종종 보는 단어인데 낯설어서 무슨 뜻인지 찾아봤다

 

요약하자면, 시간복잡도란 특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간을 의미하는데

비슷한 개념으로 특정 알고리즘이 메모리를 얼마나 차지하는지에 관련된 공간복잡도라는 것도 있다.

 

하지만 예전에 비해 컴퓨터 성능의 발달로 메모리 공간의 효율이 많이 증가했기 때문에

상대적으로 공간복잡도보다는 시간복잡도의 중요성을 더 우선하여 프로그램을 작성한다.

 

코테문제에서 시간 제한 -초, 메모리 제한 -mb 등으로 표기된 제한조건이 이와 관련된 것으로,  

보통 시간 복잡도에서는 빅-오 표기법 을 사용한다.

 

빅-오 표기법

- 알고리즘의 최악의 경우 시간 복잡도를 나타내며, 알고리즘의 성능 상한선을 표현

- 알고리즘의 실행 시간을 입력 크기에 대한 함수로 나타내는 개념

 

1. O(1) : 상수 시간 복잡도

 - 입력의 크기와 관계없이 일정한 실행 시간을 가짐

 - ex) 배열의 첫 번째 원소를 가져오는 작업

 - ex) 스택의 Push, Pop , 

 

2. O(log n) : 로그 시간 복잡도 

 - 입력의 크기에 따라 실행 시간이 로그arithmic하게 증가 (데이터가 10배가 되면, 처리 시간은 2배) 

 - ex) 이진트리

 

3. O(n) : 선형 시간 복잡도

- 입력의 크기에 비례하여 선형적으로 실행 시간이 증가

 - ex) 배열 내 모든 원소를 확인하는 경우

 - ex) for문 

 

4. O(n log n) : 선형로그 선형 시간 복잡도

- 일부 정렬 알고리즘과 같이 입력 크기에 대해 선형로그 선형으로 실행 시간이 증가합니다. 

 - ex) 퀵 정렬(quick sort), 병합정렬(merge sort), 힙 정렬(heap Sort)

 

5. O(n^2), O(n^3)... : 다항 시간 복잡도

- 입력 크기의 제곱, 세제곱 등에 비례하여 실행 시간이 증가 

 - ex) 중첩 for문 

 - ex) 삽입정렬(insertion sort), 거품정렬(bubble sort), 선택정렬(selection sort)

 

6. O(2^n), O(n!) : 지수 및 팩토리얼 시간 복잡도

- 매우 큰 입력에 대해 엄격한 제한을 가지며, 비효율적인 알고리즘 

- ex) 피보나치 수열