시간복잡도
시간복잡도는 보통 사용하는 알고리즘의 빅오 표기법을 기준으로 생각하거나, 주어지는 n의 크기를 고려했을 때 loop가 몇 차원으로 구성되는지에 대하여 계산됩니다. 아무래도 시간초과를 몇 번 겪다보면 시간복잡도에 대하여 혈안이 되는 것 같아요.
시간복잡도 파악하기
시간복잡도는 연산 시간을 파악하기 위해서인데, O(N) 기준으로 N이 1억일 때 연산이 1초 걸립니다. 만약 O(logN)이 1초 제한일 때 logN이 1억이 되려면 2의 1억 제곱이 되어야 합니다. 따라서 시간복잡도가 logN이면 N의 범위가 거의 제한이 없다고 봐도 될 것 같습니다.
반면에 개인적인 입장에서 O(log X)계열을 계산하는 건 어려웠는데, 이걸 기록해두려 합니다.
예를 들어, 계속해서 3으로 나누는 재귀 함수가 존재한다고 합시다.
def solution(n, count):
if n <= 1:
return count
return solution(n/3, count * 3)위 함수는 n이 1을 초과할 때에는 n = n / 3; count *= 3; 을 연산하고, n 이하일 때 바로 count를 출력하는 함수입니다. 비교 연산은 O(1)이므로, n이 1 초과일 때에 얼마나 재귀가 이루어지는지를 생각하면 됩니다.
시간복잡도 계산하기
차근차근 생각해봅시다. 메인함수에서 solution(N, cnt)가 호출되었을 때, N > 1 이라면 곧바로 solution(N/3, cnt)가 호출될거고, 이런 식으로 k번 함수가 호출된다고 하면 n = N/3^(k-1) 이 될 겁니다. 따라서 N/3^(k-1) <= 1일 때 함수는 cnt를 반환하면서 종료하게 될 겁니다.
그렇다면 시간복잡도는 N의 크기에 대하여 어떻게 구성될까요? N/3^(k-1) <= 1까지 재귀 연산을 수행하니까 N <= 3^(k-1)이고, 양 변에 로그를 씌워주면 logN <= k-1이 됩니다. 이를 만족하는 가장 작은 정수 k에서 연산이 끝나므로 k는 logN+1이라고 생각하면 빅오표기법으로는 O(logN)이 됩니다. 여기서 k를 가장 타이트하게 설정하면 log의 밑은 3이 될텐데, 빅오표기법에서는 더 최악으로 표현이 가능하고, 컴퓨터에서는 binary로 연산이 돌아가다보니 보통 밑을 2로 통일하여 logN(밑:2)과 같이 표현합니다.
따라서 위와 같은 경우 최종 시간복잡도가 O(logN)이 됩니다.