자료구조- 시간복잡도 & 최대 부분 배열 합
시간복잡도
시간복잡도는 코드를 작성하기 전에 실행될 코드의 수행 시간을 예측해볼 수 있게 도와주는 개념입니다. 이 개념은 입력에 대해서 작성된 코드가 얼마만큼의 시간을 사용할지를 근사적으로 알려줍니다. 시간복잡도는 Big O- O(…)으로 표기하며, 괄호 안에는 어떠한 식이나 숫자가 들어갑니다. 보통 O(n) 같이 변수 n을 이용해서 표기를 많이 하는 데 입력되는 배열의 크기 같이 입력되는 데이터의 크기를 말합니다. (그래도 표기하는 사람이 n을 정의해주는 것이 좋습니다.)
계산 방법
코드가 한 가지 동일한 동작만 한다면 시간 복잡도는 O(1)입니다.
a += 1;
b *= 2;
c = a + b;
위 코드의 시간 복잡도는 동일한 동작만 하기 때문에 O(1)입니다.
반면에 위 코드는 비슷한 동작을 하지만 반복합니다. for문은 100번을 합니다. 이유는 변수 n이 100이기 때문입니다. 따라서 for문은 반복문 안의 내용을 n번 수행합니다. 그래서 시간복잡도는 O(n)입니다. 반복문 안의 ‘…’에 해당되는 코드는 O(1)이라고 가정합니다.
위의 코드는 반복문이 중첩되어 있습니다. 중첩되면 반복문은 n * n 번 실행됩니다. 그래서 시간복잡도는 O(n²)로 표기합니다. 이렇게 n번 반복하는 반복문이 k번 중첩되게 실행되면 n^k번 반복하게 되고 시간복잡도는 O(n^k)로 표기합니다.
만일 코드 안에 여러 반복문이 있다면, 반복문 중에 가장 시간 복잡도가 가장 큰 것이 전체 시간 복잡도가 됩니다. 첫번째 반복문은 시간복잡도가 O(n-2)이고 두번째 반복문은 O(n²)입니다. 세번째 반복문 또한 시간복잡도가 O(n-2)입니다. 따라서 전체 시간 복잡도는 두번째 반복문의 시간복잡도인 O(n²)가 됩니다.
대표적인 시간 복잡도
O(1) -상수 시간 복잡도입니다. 수행 시간은 입력의 크기에 영향을 받지 않습니다.
a += 1;
b *= 2;
c = a + b;
예시는 위의 코드처럼 변수를 바로 계산하는 코드가 있습니다.
O(log n) -로그 시간 복잡도입니다. 입력 받은 데이터의 크기를 반으로 줄여 가면서 코드를 실행합니다. (이진탐색 트리하면서 정리해놨습니다.) 데이터 크기가 n이라면 계속 2로 나누면서 1이 될 때까지 코드를 실행하는데 이때 실행되는 횟수가 log n 번이고 따라서 시간복잡도는 O(log n)으로 표기합니다. 로그의 밑수는 시간복잡도에서는 표현하지 않습니다. 대표적으로 이진탐색이 O(log n)입니다.
O(√n)- 제곱근 시간 복잡도입니다. O(log n) 보다는 느리지만 O(n)보다는 빠릅니다. 소수 판별법이 대표적인 시간복잡도 O(√n) 알고리즘입니다.
위의 코드는 변수 n이 소수인지 판단하는 함수입니다. n을 2 이상 √n이하의 모든 정수로 나눕니다. 이때 n이 나누어떨어지는 경우가 없으면 n은 소수로 판별됩니다.
O(n)-선형 시간 시간복잡도입니다. 입력 받은 데이터 크기만큼 코드를 실행합니다. 일반적인 경우 선형 시간이 가장 효율적인 시간 복잡도입니다. 왜냐하면 탐색이나 답을 구하기 위해서는 데이터 전체를 한 번 쭉 살펴보는 것이 일반적이기 때문입니다.
O(n log n)- 정렬 알고리즘에서 자주 보게되는 시간 복잡도입니다. 대표적으로 퀵정렬 방법의 시간 복잡도가 O(n log n)입니다.
예시 최대 부분 배열 합
배열에 수 n개가 들어있을 때 연속된 부분 배열의 최대합(maximum subarray sum)을 구하는 문제입니다. 배열에서 연속해 있는 값들을 택하여 그 합을 최대로 만드는 것 입니다. 음수가 포함되어 있음을 고려해야 합니다.
시간복잡도가 O(n³)인 풀이 방법
반복문을 세 번 중첩해서 돌리면서 모든 부분 합을 비교합니다. 입력된 배여을 한 번씩 살펴보는 반복문이지만 시간복잡도가 O(n³)이기 때문에 입력되는 데이터가 100 이상일 경우 시간복잡도가 1000000 이상이 됩니다.
시간복잡도가 O(n²)인 풀이 방법
부분 배열을 오른쪽으로 이동해서 동시해 그 합도 같이 계산하게 해서 시간복잡도를 개선했습니다. 반복문 한 번 줄여서 시간복잡도는 O(n²)가 되었습니다.
시간복잡도가 O(n)인 풀이 방법
동적계획법을 활용해서 시간복잡도를 O(n)으로 단축하였습니다. i번째 까지 연속부분 배열의 최대합은 i번째 배열이거나, (i-1)번째 까지 연속부분 배열의 최대합과 i번째 합, 둘 중에 하나입니다. array[i] or sum + array[i] 중에 큰 값이 i번째까지 연속부분 배열의 최대합입니다. 따라서 for문 한번으로 문제를 해결하였고 시간복잡도는 O(n)으로 단축하였습니다.
