복잡도란?#

• 알고리즘의 성능, 효율성을 나타내는 척도이다.
• 시간, 공간 복잡도로 나뉜다.
• 특정 크기의 n(입력값)을 기준으로 수행시간, 사용공간이 얼마나 되는지 객관적으로 비교할 수 있는 기준 제시한다.

시간복잡도#

특정 크기를 입력했을 때 필요한 연산의 횟수
알고리즘 성능으로는 Best case, Average case, Worst case 가 있다.
알고리즘이 복잡해질수록 평균을 구하기 어려워져서 최악의 경우로 성능을 파악한다.

공간복잡도#

프로그램을 실행, 완료 했을때 얼마나 많은 메모리가 필요한지를 나타낸다.
알고리즘을 실행시키기 위한 공간으로는 고정공간, 가변공간이 있다.

고정공간 : 코드가 저장되는 공간, 알고리즘과 무관하다.
가변공간 : 변수를 저장하는 공간, 알고리즘과 밀접하다.

알고리즘의 성능을 판단할 때는 보통 시간 복잡도를 사용한다.

빅오 표기법#

복잡도를 나타내는 점근 표기법 중 가장 많이 사용되는 표기법이다.
가장 많이 사용되는 이유는 최악의 경우를 가장 쉽게 고려할 수 있다.
O(1)은 입력에 대해 변하지 않아 상수시간, O(n)은 선형시간이다. 빅오 표기법의 정의
O(g(n))는 “f(n)이 결국 g(n)보다 크지 않다.
즉 빅오 표기법은 아무리 나빠도 비교하는 함수와 같거나 좋다.
그래프는 아래 있을수록 성능이 좋다.

빅오 표기법의 규칙#

• 상수 곱의 법칙 : f(n)의 빅 오 표기법은 상수 𝑘 에 영향을 받지 않는다.
• 함수의 합의 법칙 : 두 함수의 합의 빅 오 표기법은 각 함수의 빅 오 표기법의 합과 같다.
• 함수의 곱의 법칙 : 두 함수의 곱의 빅 오 표기법은 각 함수의 빅 오 표기법의 곱과 같다.
• 다항식의 법칙 : 다항식의 최고차 항에 의해 빅 오 표기법이 결정된다.

빅오 표기법 특징#

1. 상수항을 무시한다. O(99n)은 O(n) 으로 본다.
2. 영향력 없는 항은 무시한다. 가장 영향력이 큰 항 이외의 항은 무시한다.
   • f(n)=3n^3 + 4n^2 + 5n + 6 에서 가장 큰 것은 n^3 따라서 O(n^3) 으로 본다.

시간복잡도와 빅오 표기법#

시간복잡도는 입력을 기준으로 실행하는 연산의 횟수임으로 연산의 횟수를 세면 된다.(횟수를 셀때는 알고리즘에서 핵심이 되는 연산의 횟수만 세면 된다.)

상수함수 < 로그함수 < 선형함수 < 다항함수 < 지수함수
O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n)
왼쪽에서 오른쪽으로 갈수록 성능이 떨어진다.