빅오 빅세타 빅오메가, 시간복잡도, 공간복잡도에 대해 정리

1.빅오 big-O
------
알고리즘의 성능 및 복잡도를 표현하기 위하여 사용하는 지표
알고리즘의 실행 시간 또는 사용 메모리 공간을 표현
정확한 값이 아닌 어림 값으로, 알고리즘의 대략적인 평가만 가능

 a.상한점근, 최악의 경우 표기법이라 함, 최악의 경우에도 이보단 빠르다는것
  최악의 경우라는 것은 모든 경우라고 할 수 있기 때문에 신뢰도가 높아
   가장 일반적으로 사용되는 표기법이다.
 b.표기법 - 모든 n, n=> n0에 대해
   f(n) <=cg(n)인 조건을 만족시키는
    두 양의 상수 c와 n0가 존재하기만 하면 f(n) = O(g(n))이다.

***
2.빅세타 big-Θ
------
 a.알고리즘의 평균(중간) 상태를 나타냄
***
3.빅오메가 big-Ω
--------
 a.하한점근, 최선의 경우 표기법

***
4.시간복잡도
----------
 a.알고리즘을 프로그램으로 실행하여 완료하는 데 걸리는 시간
   프로그램의 컴파일 시간과 실행 시간의 합으로 표현

 b.알고리즘 간의 비교를 위한 것이므로 정확한 실행 시간을 추정하여 사용x 실행 빈도수 사용o

 ex)피보나치 수열 (이전의 두 항의 합으로 다음의 새로운 항이 만들어지는 수열
   첫번째 항 f0 , 다음항 f1  -> f0=0, f1=1  일반항 fn은 fn-1 + fn-2 (단,n=>2)이 된다.

 \`피보나치 수열 알고리즘
 if(n<0) then
  stop;
 if(n=<1) then
  return n;
 f1 = 0;
 f2 = 1;
 for(i=2; i<=n; i=i+1) do{
  fn=f1+f2;
  f1=f2;
  f2=fn;
 }
 return fn;
 end `\

***
5.공간복잡도
----------
 a.알고리즘을 프로그램으로 실행하여 완료하는 데 필요한 총 저장공간
    -필요한 고정 공간과 가변 공간을 합하면 구할 수 있다.
 
 b.고정공간
   프로그램의 크기나 입출력의 횟수에 상관없이 고정적으로 필요한 저장공간
   프로그램의 저장공간과 변수 및 상수들을 저장하기 위한 공간

 c.가변공간
   실행과정에서 사용하는 데이터와 변수들을 저장하는 공간
   함수 실행에 관련된 정보를 저장하는 공간

 

*빅데이터 처리관련으로 공간복잡도가 중요시 되고있다.