1. Big-O 표기법이란?
알고리즘의 성능을 수학적으로 표기해 시간, 공간 복잡도 나타내 줄 수 있다.
a. 시간 복잡도란
시간 복잡도(Time Complexity)는 알고리즘이 입력받는 데이터의 수 혹은 크기를 변수로하여 실제로 수행되는 연산량을 수식 형태로 표기하는 것을 말한다. 시간 복잡도는 주로 빅-오 표기법(Big-O Notation)을 사용한다.
1) O(1)알고리즘 : constant time
데이터의 크기에 상관없이 성능의 변화가 없는 경우
문제 :
2) O(n) 알고리즘 :
데이터의 크기에 따라 비례해서 처리시간도 증가한다.
3) O(n^2) 알고리즘 : quadratic time
-> 지수함수형식
4) O(nm) 알고리즘 3)이랑 차의 주의
5) O(n^3)
6) O(2^n) : exponential time
ex) 피보나치수열
7) O(log n)
: ex) 이진 탐색 그러나, balance가 맞지 않아 한쪽으로 몰려있을 때 O(n)이다.
8) O(sqrt(n))
문제:
9) big-o에서 상수는 과감하게 버린다.
O(2n) -> O(n)