시간복잡도 logN에 대한 경우의 수 및 메모리 사용량

알고리즘에서 logN의 밑은 2이므로 

만약 N이 10억이라고 할 때, N = 10억 = 10^9

log2N = log2(10^9)가 된다.

 

이건 다시

9log2(10)이 되는데 log2(10)은 3.3정도로 생각하면 되므로

9*3.3 = 약 30이라는 결과를 얻을 수 있다.

 

만약 문제가 MlogN의 시간복잡도를 요구하는데 M이 200,000이었을 경우

MlogN = 20만 * 30 = 6,000,000이 된다.

 

메모리 사용량은 1000 = 1KB. 

1,000,000 = 1MB가 되므로 MlogN의 메모리 사용량은 약 6MB가 된다는 것을 알 수 있다.