점근 표기법(asymptotic notation) : 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수론과 해석학의 방법이다.
빅오(상한선을 기준), 빅오메가(평균적인 값), 빅세타(하한선을 기준)
빅오(Big - O) : 알고리즘의 효율성을 나타내는 지표., “계산 복잡도 이론”, “시간 복잡도”를 나타낼 때 사용한다.
알고리즘의 효율성은 데이터를 가지고 연산을 하는 횟수를 의미함.
알고리즘 효율성의 상한선을 기준으로 표기한다.(그러나 이 상한선이 꼭 최악의 경우인 것은 아니다.)
시간 복잡도 : Big - O에 대한 시간 개념.
알고리즘의 수행 시간이 얼마인지를 나타냄.(연산의 수를 계산, 중요하지 않은 값들은 무시)
반복문을 기준으로 입력 값(N)에 영향을 받는 핵심적인 코드가 어느 부분인지를 파악하고 N과 어떤 관계가 있는지를 파악하는 관점을 기르는 것이 중요
입력되는 데이터는 입력이 충분히 큰 것이라 가정. 중요하지 않은 값들이 생기게 된다.
- 상수항
O(2N) -> O(N)
O(N² + 2) -> O(N²) - 영향력이 적은 항
O(N² + N) -> O(N²)
공간 복잡도 : 알고리즘이 공간을 얼마나 차지하는가.(메모리를 얼마나 차지하는지)
크기가 N인 배열의 공간 복잡도는 O(N)
크기가 N인 2차원 배열의 경우 O(N²)
파이썬 기준 리스트 내부 메소드의 시간 복잡도
탐색이 필요한 경우 기본 O(n)이 필요.
일반으로 연산 횟수가 10억이 넘어가면 C 언어를 기준으로 통상 1초 이상의 시간이 소요된다.
파이썬에선 1000만이 1초, 2초는 3000만 가량 까지 가능 한듯 보인다.
int a[1,000] = 4KB
int a[1,000,000] = 4MB
int a[2000][2000] = 16MB
리스트는 1000만 단위가 넘어가지 않아야 한다.(128MB정도)
계산 복잡도 이론에 대한 공부가 필요하다...
