728x90 반응형 o(nlogn)1 [알고리즘] 왜 시간복잡도에 로그가 들어가지? O(nlogn)?.. 많은분들이 시간복잡도 하면 보통 O(logn) 으로 표현되니 그런가보다..(와이와이???) 하고 넘기실텐데 로그가 왜 들어가는지 의아하신 분들을 위한 글 입니다. 앞선 글에서 분할 정복 알고리즘을 설명한 바 있습니다. 예를 들어봅시다. (배열을 반으로 나누는 과정은 매 단계마다 배열을 절반으로 나눕니다 따라서 주어진 배열의 크가 n 일때) Step 1 : n을 2로 나눕니다 (n/2) Step 2 : n/2를 다시 2로 나눕니다 (n/2) Step 3 : n/4를 다시 2로 나눕니다 (n/8) 이러한 과정을 k 번 반복하여 배열의 크기가 1이 될때까지 반으로 나눈다. 이 과정에서 배열의 크기가 1이 될때까지 몇번의 나누기가 필요한가요? 위 과정에서 배열의 크기가 1이 되기 위해서는 앞선 Step 에서 분.. 2023. 12. 3. 이전 1 다음 728x90 반응형
