시간 복잡도

Dec 19, 2023

💡

log2(2의n승숫자) = n 의 시간 복잡도는 n이다

log2(16)=4

2의 8승 = 256

2의 16승 = 65536

2의 n승 = 무한대

제곱된 값은 기하급수적으로 커지는데

너무 숫자가 커지면 int에 들어가지 않기 때문에 log로 표현한다.

💡

이진 트리 검색은 시간 복잡도가 선형적으로 증가하지 않는다.


System.out.println("시간 복잡도: " + Math.log(N) / Math.log(2));

O(N) = 풀스캔

O(logN) = 이진 트리 검색

💡

이정도는 외워라! 2의 8승은 256

2의 10승 1024

2의 16승 65536

2의 32승 4290000000

💡

랜덤 엑세스가 풀 스캔보다 유리한 때는 15% 미만일 때 까지만이다.(이진 트리는 랜덤 엑세스 방식)

총 데이터의 개수가 20개라고 치자.

랜덤 엑세스 방식으로 데이터를 찾으면

데이터 1개를 찾을 때는 5번, 2개를 찾을 때는 10번, …, n개를 찾을 때는 5n번 만에 찾을 수 있다.

풀 스캔 방식으로 찾으면 1개를 찾든 2개를 찾든 20번 만에 찾을 수 있다.

여러 개의 데이터를 찾으려면 풀 스캔 방식이 유리할 수도 있다.

More articles