[알고리즘] 왜 시간복잡도에 로그가 들어가지? 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 에서 분모를 보면 (n/2, n/2^2, n/2^3,...n/2^k) 이렇게 커지는거 보이시나요?

 

그러면 n/2^k = 1 이 되어야 할것이고

n=2^k

이제 각 항에 밑이 2인 로그를 씌워주면

logn = k (밑 2)

따라서 k는 logn 이되네요

 

여기서 logn은 k, k 가 몇번 반복한지에 대한 횟수였던거 기억하시죠?

이에 대한 시간복잡도는 O(logn)  으로 해당 시간 소요됨을 알 수 있습니다.

 

이에대한 간단한 파이썬 코드로도 확인해보면

def split_array(arr):
    count = 0  # 배열을 반으로 나누는 횟수를 저장할 변수

    # 주어진 배열의 크기가 1보다 큰 경우 반복하여 반으로 나눕니다.
    while len(arr) > 1:
        arr = arr[:len(arr)//2]  # 배열의 절반 부분을 선택하여 나눔
        count += 1  # 배열을 나눈 횟수 증가
    
    return count

# 예시 배열
example_array = [1, 2, 3, 4, 5, 6, 7, 8]

# 배열을 반으로 나누는 횟수 출력
result = split_array(example_array)
print("배열을 반으로 나누는 횟수:", result)

 

이와 같이 코드의 함수 split_array는 배열을 반으로 나누는 과정을 반복하고 

주어진 배열의 크기가 1일때까지 반복하여 배열을 반으로 나누는 과정을 반영하고 있네요!

이 횟수는 입력된 배열의 크기에 대하여 로그 시간 복잡도 O(logn)을 나타냅니다.