시간, 공간 복잡도 Big-O 표기법

Big-O 란?

• 알고리즘의 성능을 수학적으로 표기해주는 표기법.
• Input에서 Ouput으로 결과 값이 나오는 시간.
• 알고리즘의 "시간" 과 "공간 복잡도" 를 표현할 수 있다.

왜 써요? 🧐
우리는 다른 사람이 만든 알고리즘을 자주 사용하게 될 것이다. 그런 경우에는 그 알고리즘이 얼마나 빠른지 알아야한다.(최적화)

Big-O 표기법은 알고리즘의 실제 running time을 표기하기 보다는 "Data" 또는 "사용자의 증가율"에 따른 알고리즘의 성능을 예측하는 것이 목표이다. 그렇기 때문에 상수와 같은 숫자들은 모두 " 1 " 이 된다.

O(1)

입력 Data 크기와 상관없이 항상 일정한 시간이 걸리는 알고리즘.

☘️ O(1)의 시간 복잡도를 가진다.

O(logN) : 로그

0(logN) :
log : 로그 란 : 4는 22 를 제곱한다 4. 16 은 44를 제곱한다. 이것을 log로 표현한다.
log2^4 = 2 : 4가 되기 위해서 두번 제곱해야하는데 그 수가 2이다.
다시 말해 2라는 수를 몇번 제곱해야 4가 되느냐.

보통은 2^2 =4 로 표현하는데, log로 표현하면

log가 생긴 목적은 이러하다.
소수인 3,5,7 은 어떤 수를 제곱해야 이 수들이 나오는지 알 수 없다. 이런 것들을 표현하기 위해 log를 사용한다.
N 에 입력된 값에 16이라 가정할때 0(log 16).

0(log 16) : 답 4 (N에 16이 들어왔는데 log표기법으로 들어온 값이 16 -> 4 로 작아졌다)

O(n) 직선 선형

n에 넣은 값만큼 된다. 16을 넣으면 O(16)

O(NlogN) 선형로그

16log16 => 16 x 4

O(N^2) 제곱

N = 16, 16^2 = 256

O(2^N) 지수 (N의 n제곱)
6만5천~...