[맛있는물회] CH01_자료구조와 알고리즘

1. 시간복잡도(Time Complexity)와 공간복잡도(Space Complexity)

 ㅇ속도에 해당하는 알고리즘의 수행시간 분석결과를 가리켜 -->'시간복잡도' 라고 한다.
-> 연산의 횟수를 세어서 T(n)을 구성한다.

<빅-오 표기법(Big-Oh Notation)>
보통 n의 증가 및 감소에 따른 T(n)의 변화 정도를 나타낸다.
O(I) - 상수형 빅오. 연산횟수가 고정인 유형의 알고리즘. O(3)라도 O(I)라고 표현한다.

O(logn) -  데이터 수의 증가율에 비해 연산횟수의 증가율이 훨씬 낮은 바람직한 유형의 알고리즘.

O(n) - 데이터 수와 연산횟수가 비례

O(nlogn) - 선형로그형 빅오. 데이터가 두 배로 늘때 연산횟수는 두배를 조금 넘게 증가. 알고리즘 중 이에 해당하는 알고리즘이 적지 않다.

O(n^2) - 이중으로 중첩된 반복문 내에서 연산이 진행되는 경우. 즉, 중첩된 반복문의 사용은 알고리즘 디자인에서 그리 바람직하지 못하다.

O(n^3) - 이 역시 그냥 적용하기엔 무리가 있는 알고리즘이다.

O(2^n) - 사용한다는 것 자체가 비현실적인 알고리즘이다. 매우 무서운 연산횟수의 증가를 보인다.

ㅇ메모리 사용량에 대한 분석결과를 가리켜 -->'공간 복잡도' 라고 한다.

*O(n)의 알고리즘을 O(logn)의 알고리즘으로 개선시키는 것은 약간의 개선이 아닌, 혁신적인 성능의 개선으로 간주된다.



2. 빅 오의 수학적 판별법


"두 개의 함수 f(n)와 g(n)가 주어졌을 떄, 모든  n>=K에 대하여 f(n)<=Cg(n)을 만족하는 두 개의 상수 C와 K가 존재하면, f(n)의 빅오는 O(g(n))이다."

ex) T(n) = 7n³ + 3n² + 2  --> O(n³) 임이 옳음을 수학적인 정의를 근거로 증명하시오

sol)
n>=0  7n³<=7g(n)
n>=3  3n²<=3g(n)
n>=2      2<=2g(n)

--> f(n)<=12g(n)