[개발 지식] [알고리즘] 시간복잡도란?

 

시간복잡도 ?

시간복잡도는 알고리즘과 큰 연관이 있다.

알고리즘은 문제를 해결하기 위한 방법이다.

시간복잡도는 코드를 작성하기 전에 실행될 코드의 수행 시간을 예측해볼 수 있게 도와주는 개념이다.

알고리즘의 예)

온라인 코딩 테스트 알고리즘 풀기

아침 일어나서 회사 가는 방법

점심 메뉴를 고르는 방법

표기법 : 보통 BigO라는 방식으로 표기한다. (빅오메가, 빅세타, 빅오 세 가지가 있다.)

빅오 표기법은 최악의 실행시간, 가장 느린 케이스를 나타내는 것이다.

일반적으로 접근 표기법을 이용하여 나타낸다.

의미 : 시간 소요가 아닌 조작(연산)되는 횟수 (공간복잡도는 사용하는 메모리)

계산되는 양에 따라 시간이 얼마나 걸릴지를 나타내는 것이다.

---

빅오 표기법 시간복잡도 수행시간이 낮은 것 부터 높은 것 순서 

(뒤로 갈 수록 점점 오래 걸리는 순서이다)

N = 입력된 수

O(1) > O(logN) >  O(N) > O(NlogN) > O(N^2) > O(2^N) > O(n!)

===

상수 시간> 로그 >  직선(선형) > 선형로그 > 제곱 > 지수(N의 n제곱) > O(n!)

===

O(1)

: n이 몇개 있든 실행시간이 일정한 것

 

O(logN) 

: logn은 n을 절반으로 나눌 수 있는 수

ex> 이진 탐색으로 값을 찾을 때

 

O(N)

: 입력 받은 데이터 크기만큼 코드를 실행한다. 일반적인 경우 선형 시간이 가장 효율적인 시간 복잡도이다.

ex>병합 정렬을 통해서 값을 정렬할 때

 

O(NlogN)

: 정렬 알고리즘에서 자주 보게되는 시간 복잡도이다.

대표적으로 퀵정렬 방법의 시간 복잡도가 O(n log n)이다.

 

O(n^2)

: 이중 for문을 이용해서 n개의 값을 n번 대입해야 하는 수행시간

ex> 배열 a값이 배열 b에 있는지 확인할 때

 

O(2^n)

: 2의 n제곱만큼 늘어나므로 n이 늘수록 정말 가파른 수행시간을 가지는 것

ex> 피보나치 수열, 재귀 탐색으로 값을 찾을 때

 

O(n!)

: 최악의 수행시간을 가지는 것

ex> 팩토리얼

 

입력의 크기가 커질수록 수행시간의 차이는 커진다.