1장 자료구조와 알고리즘의 이해 - 빅오 -

1. 빅오 표기법이란? Big-Oh Notation

 T(n)에서 가장 영향력이 큰 부분을 제외하고 모든 부분은 생략하는 것을 뜻한다.

 ex) T(n) = n^2 + 2n + 1 일 때 n^2을 제외한 나머진 버린다.

  표기는 O(n^2).

 왜 그런지는 n^2의 비율을 따져보면 쉽게 이해가 된다.

2. 대표적인 빅오

 - O(1) : 상수형 빅오, 데이터수와 상관없이 항상 일정한 연산을 한다.

 - O(logn) : 로그형 빅오이다. 데이터 수의 증가율에 비해 연산횟우의 증가율이 현저히 낮은 형태

 - O(n) : 선형 빅오. 데이터의 수 == 연산횟수가 되는, 즉 비례가 되는 알고리즘을 뜻한다.

 - O(nLogn) : 선형로그형 빅오. 데이터의 수가 두배가 될 때 연산횟수가 두 배를 조금 넘는 알고리즘이다. 

 - O(n^2) : 이렇게 나오면 당연히 로그형 빅오가 되기 위해 노력을 해야한다.

 - O(n^3) : 마찬가지.

 - O(2^n) : 지수형 빅오. 지수적 즉가라는 매우 무서운 연산횟우의 증가를 보이기 때문에 반드시 개선이 필요하다.

3. 수학적 증명

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

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