시간복잡도(Time Complexity)

: 입력의 개수가 n개일 때 알고리즘의 실행 시간을 n에 대한 함수로 표현한 것, 보통 최악의 경우(가장 연산을 많이 해야 되는 경우)로 함수를 표현한다.
-> 정렬을 할 때, 내림차순을 오름차순으로 만들 경우 최악의 경우가 되겠다.

[ 시간복잡도 함수: T(n)=2n의 의미에 대해 알아보자! ]

2n = {(반복문 내부 상수 시간 연산 2개)를 n번 반복 } or
{(반복문 내부 상수 시간 연산 1개)를 n번 반복, 이러한 반복문이 2개}
n은 입력의 개수이고 반복문에서 입력한 개수만큼 처리해야 되니까 상수 시간 연산을 n번 반복하는 것!

[ 시간복잡도 함수: T(n)=2n^2, 5n^2, 100n+5에 대해 알아보자! ]

2n^2와 5n^2는 상수 배의 차이가 난다. 이렇게 상수 배의 차이가 날 때는 비슷하다고 취급한다.
2n^2와 100n+5와 같이 n^2와 n배의 차이가 날 때는 구별해야 한다.
(n이 커질수록 너무 차이가 커지기 때문)

-> 2n^2, 5n^2 따위는 O(n^2)로 동일하게 표현한다! / O(n^2) = n^2으로 늘어나는 정도이다.
(실제로는 n^2의 2배,5배인데 상수 배이므로 비슷하다고 처리)
->100n+5는 O(n)으로 표현한다. / O(n) = n이 늘어나는 정도이다
(실제로는 n의 100배이나 상수 배이므로 비슷하다고 처리)

빅오표기법

상수 c와 n0가 존재하여, n>=n0인 모든 n에 대하여 T(n)<=c*f(n)을 만족하면 T(n)=O(f(n))이라고 한다.

Ex)
T(n)=2n^2=O(n^2) -> T(n) <= 2n^2, n>=1 을 만족하므로 성립한다. <n0=1, c=2>
T(n)=5n^2+4=O(n^2) -> T(n) <= 6n^2, n>=100 을 만족하므로 성립한다. <n0=100, c=6>
T(n)=100n+5=O(n) -> T(n) <=200n, n>=100 을 만족하므로 성립한다. <n0=100, c=200>

다른 표기법

빅오메가표기법: 상수 c와 n0가 존재하여, n>=n0인 모든 n에 대하여 T(n)>=c*f(n)을 만족하면 T(n)= Ω(f(n))이라고 한다.

빅세타표기법: T(n)=O(f(n))이고 T(n)=Ω(f(n))이면 T(n)= θ(f(n))이라고 한다.
(=) 상수 c와 n0가 존재하여, n>=n0인 모든 n에 대하여 T(n)<=c1*f(n), T(n)>=c2*f(n)을 만족하면 T(n)= θ(f(n))이라고 한다.

Ex)
T(n)=2n^2=Ω(n^2) -> T(n) >= 1n^2, n>=1 을 만족하므로 성립한다. <n0=1,c=1>
->T(n)=2n^2이 O(n^2)와 Ω(n^2)으로 동일하게 성립한다 -> θ(n^2)으로 표현이 가능하다! <n0=1, c1=2, c2=1>

[ 응용 Part ]

Q. T(n)=3n^2-100n+6일 때 O(n^3)이라고 쓸 수 있을까?
-> T(n)<=3n^3, n>=100 을 만족하므로 성립한다. <n0=100, c=3>

Q. T(n)=3n^2-100n+6일 때 Ω(n)이라고 쓸 수 있을까?
-> T(n)>=1n, n>=100 을 만족하므로 성립한다. <n0=100, c=1>

// T(n) = O(n^2) = Ω(n^2)이지만, T(n) != Ω(n^3), T(n) != O(n)을 만족하지 못 하므로 T(n) = θ(n^2)만 성립한다.

시간 복잡도 분류

다항 시간: O(1), O(logn), O(nlongn), O(sqrt(n)),O(n^2),O(n^3)
<n이 커져도 시간이 (상대적으로) 적게 걸림>

지수 시간: O(2^n), O(n2^n), O(n!)
<n이 커지면 시간이 오래 걸림>