[알고리즘] 시간복잡도와 공간복잡도 (빅오 표기법)

어떤 알고리즘의 성능을 평가할 수 있는 방법은 두 가지가 있다.
시간복잡도와 공간복잡도이다.

사실, 시간복잡도와 공간복잡도의 성능 모두 좋으면 Best👍겠지만 어려운 일이다.
(시간복잡도와 공간복잡도는 함께 할 수 없는 반비례 관계라고 들은 것 같기도)
둘 중 누가 더 중요하냐고 물어보면 당연 시간복잡도다.

• 시간복잡도 : 알고리즘의 실행 속도
• 공간복잡도 : 알고리즘의 메모리 사이즈

① 빅오(Big-O)표기법 : 최악의 실행 시간
② 오메가(Big-Ω)표기법 : 최상의 실행 시간
③ 세타(Big-θ)표기법 : 평균 실행 시간


우리는, 빅오 표기법을 사용하게 되는데 그 이유는 Worst 실행시간이어도 그 시간은 보장해줄 수 있기 때문이다.

Big-O에서 가장 중요한 것은 "반복"이다.
반복을 통해 n의 차수를 구할 수 있다.

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(2^n) < O(n!)

상수를 가진 O(1)이 가장 좋은 시간복잡도가 되고, O(n!)는 지양해야하는 시간복잡도이다.

for(int i=0;i<10;i++)
	System.out.println("안녕하세요");
    
    
for(int j=0;j<n;j++)
	System.out.println("안녕하세요");

같은 기능을 하는 for 문이 2개 있지만 두 개의 Big-O는 다르다.
위는 10번 반복이 정해져있는 O(1)이고, 아래는 n번 반복하는 O(n)이 되는 셈이다😅

그렇다면 중첩반복문은 어떨까?

for(int i=0;i<4;i++){
	for(int j=0;j<n;j++)
		System.out.println("안녕하세요");
    }

첫 번째 반복문에서는 4번 반복하지만, 두 번째 반복문에서는 n만큼 반복한다.
전체적으로 4n번 반복하지만, 상수는 모두 제거하기 때문에 시간복잡도는 O(n)이 된다.

만약, 4n+3이어도 시간 복잡도는 O(n)이 된다.
그렇다면 3log2+3n^2이라면 시간복잡도는 어떻게 될까? 😖_

어렵게 느껴질 수 있지만, 빅오의 정의인 최악의 경우를 생각하면 된다. O(logn)보다 O(n^2)이 최악이므로 시간복잡도는 O(n^2)이 된다. 참 쉽죠?😻