[알고리즘] 빅오 표기법(Big-O Notation), 시간복잡도, 공간복잡도

시간복잡도와 공간복잡도

시간복잡도

▷ 속도에 해당하는 알고리즘의 수행시간 분석결과

공간복잡도

▷ 메모리 사용량에 대한 분석결과

※ 일반적으로는 중요도는 실행속도가 메모리 사용량보다 중요하다.

※ 알고리즘의 성능을 판단하는 데 있어서 중요한 것은 '최악의 경우'이다.

빅-오 표기법(Big-O Notation)

▷ 빅-오는 시간 복잡도 T(n) 에서 가장 영향력이 큰 부분을 따지는 것이다.

▷ 데이터 수의 증가에 따른 연산횟수의 증가형태를 나타내는 표기법이다.

ex) T( n² + 2n + 1 ) 일 경우 빅-오 표기법으로는  O( n²) 이 된다.

빅-오 표기법의 성능(수행시간, 연산횟수)

O( 1) < O( log n) < O( n) < O( n* log n ) < O( n²) < O( n³)  < O( 2ⁿ ) < O( n! ) 

• O( 1)  : 상수형 빅-오, 데이터 수에 상관없이 '연산횟수가 고정'인 유형의 알고리즘을 뜻한다.
• O( log n)  :  로그형 빅-오, '데이터 수의 증가율'에 비하여 '연산횟수의 증가율'이 훨씬 낮은 알고리즘
• O( n)  : 선형 빅-오, 데이터 수와 연산횟수가 비례하는 알고리즘
• O( n* log n )  : 선형 로그형 빅-오, 데이터의 수가 2배로 늘 때, 연산횟수는 2배 조금 넘게 증가하는 알고리즘
• O( 2ⁿ )  : 지수형 빅-오, '지수적 증가'는 무서운 연산횟수의 증가를 보이기 때문에 다른 방안을 찾아야한다.

빅-오에 대한 수학적 접근

"두 개의 함수 f(n) 과 g(n) 이 주어졌을 때, 모든 n >= K에 대하여 f(n)  <= Cg(n) 을 만족하는

  두 개의 상수 C와 K가 존재한다면, f(n) 의 빅-오는 O(g(n)) 이다."

예를 들어 f(n) = 5n² + 100,   g(n) = n² 일 때  K(=10), C(=6) 가 존재하기 때문에  f(n) 의 빅-오는 O( n²)

이는 연산횟수의 증가율의 증가패턴은 함수의 차수와 중요한 것을 알 수 있습니다.

정리

※ 알고리즘에서는 보통 1억번을 1초로 잡는다.

※ 알고리즘의 수행 시간은 '반복문'이 지배한다.

연산의 입력이 큰 경우에는 차수를 줄여버리는게 가장 중요합니다. O( log n) , O( n) 를의 복잡도로 짜는 버릇을 

들이는게 중요합니다. 

또한 다시 한 번 정리하면, 일반적으로는 중요도는 실행속도가 메모리 사용량보다 중요하기 때문에, 시간복잡도를

항상 생각해야 합니다.

정렬 알고리즘을 바탕으로 시간복잡도와 공간복잡도를 이해하는 것도 좋은 방법으로 생각된다.

향후 포스팅에서 정렬 알고리즘을 소개할 경우 내용을 정리해서 복잡도에 대한 내용도 추가하겠습니다.

참고

1. 윤성우의 열혈 자료구조
2. http://baactree.tistory.com/26?category=732753
3. https://kks227.blog.me/220785731077