[알고리즘] 알고리즘 복잡도(시간복잡도,공간복잡도)

왜? 배우는가

하나의 문제를 푸는 알고리즘은 다양할 수 있다 이 다양한 알고리즘 중 어느 알고리즘이 더 좋은지 분석하기 위해, 복잡도를 정의하고 계산한다.

종류

시간복잡도 : 얼마나 빠르게 실행되고 결과를 도출하느냐

공간복잡도 : 얼마나 공간(메모리 사이즈)을 쓰느냐

 

둘 중에 더 중요한 것은 시간복잡도이다. 왜냐하면 요즘은 메모리가 매우 커졌기 때문에 시간복잡도보다는 중요도가 후 순위이다.

 

시간복잡도의 주요요소

 - 반복문이 주요요소이다. 즉 반복문이 가장 영향을 많이 미친다.(입력의 크기가 커지면 반복문이 알고리즘 수행시간을 지배한다.)

 

그러면 시간복잡도를 우리 눈에 보기 좋게 객관적으로 표현을 해야 비교가 가능하다. 그래서 나온것이 빅오 표기법이다.

 

알고리즘 성능 표기법

Big O (빅-오) 표기법: O(N)

• 시간복잡도인데 알고리즘의 최악의 경우인 실행 시간을 표기한다. 왜나하면 가장 최악의 상황이라도 이 정도의 선능은 보장한다는 의미이기 때문이다.

다른 표기법들은 Ω (오메가) 표기법: Ω(N), Θ (세타) 표기법: Θ(N) 들이 있는데 최상의 실행시간, 평균실행시간을 표기한다.

 

형식 : O(입력)

• 입력 n 에 따라 결정되는 시간 복잡도 함수
• O(1), O(logn), O(n), O(nlogn), O(n2), O(2n), O(n!)등으로 표기함
• 입력 n 의 크기에 따라 기하급수적으로 시간 복잡도가 늘어날 수 있음
  • O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(2^n) < O(n!)

    

    빅오 표기법

• 단순하게 입력 n에 따라, 몇번 실행이 되는지를 계산
• n^2+1000 또는 100n^2-100 일때의 빅오는 O(n^2)이다. 최고차항으로만 표시하고 계수는 생략한다.

 

O(1)는 일정한 복잡도로, 입력값이 증가하더라도 시간이 늘어나지 않는다

O(n)은 선형 복잡도로, 입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것을 의미한다.

O(log n)은 로그 복잡도로, O(1) 다음으로 빠른 시간 복잡도를 가진다.

O(n^2)은 2차 복잡도로 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는 것을 의미.

O(2^n)은 기하급수적 복잡도로 가장 느린 시간 복잡도이다.