Time Conplexity : 시간복잡도
1. 시간복잡도는 무엇이고 왜 필요할까?
복잡도 분석(complexity analysis)는
알고리즘이 시간과 공간을 얼마나 차지하는지 분석하는 것이다.
왜 중요한가?
시간과 공간의 복잡도는 그 알고리즘이 얼마나 효율적인지를 나타낸다.
어떤 문제를 풀기 위한 다양한 방법이 있고, 그 중 어느 방법이 가장 효율적인지
확인해 볼 수 있는 지표가 됩니다.
만약 시간과 공간의 제한이 없다면 알파고를 만드는 것도 어렵지 않습니다.
무한의 공간에 모든 경우의 수를 저장하고,
연산에도 무한의 시간을 써 필요한 경우의 수를 찾아내면 되니까요.
하지만 우리에게 주어진 공간과 시간은 한정적이기 때문에
어떤 문제를 해결할 때 복잡도를 고려해야 합니다.
물론 가장 중요한 건 알고리즘이 제대로 작동하는가입니다.
그 다음에 조금 더 효율적인 방법은 없을지 고민해 볼 수 있습니다.
복잡도 분석 중 시간복잡도에 대해 먼저 알아보겠습니다.
문제의 크기가 커질수록 문제를 푸는 시간은 대체로 증가합니다.
방법에 따라 크기가 커질 때 문제를 푸는 시간이 빠르게 증가할 수도 있고, 비교적 천천히 증가할 수도 있습니다.
다음의 예제를 통해 알아보겠습니다.
* 배열에서 가장 큰 차수(difference) 구하기
배열이 주어졌을 때, 가장 큰 차수를 구하는 방법에 대해 생각해보겠습니다.
aproach 1) 모든 숫자 비교하기
주어진 값이 7개일 때, 모든 숫자를 비교하는 연산을 7X7번 수행합니다.
만약 100개의 값이 주어지면 100X100번 연산을 수행합니다.
따라서 approach 1은 input size가 n일 때, n^2번의 연산을 수행합니다.
approach 2) 가장 큰 수와 가장 작은 수를 찾기
가장 큰 차수는 가장 큰 수에서 가장 작은 수를 뺀 것과 같으므로 모든 숫자를 비교하지 않고,
가장 큰 수와 가장 작은 수만 찾으면 이 문제를 해결할 수 있습니다.
주어진 값이 7개일 때, 가장 작은 수인지 아닌지 판별하는 연산을 7번 수행합니다.
마찬가지로 가장 큰 수인지 아닌지 판별하는 연산을 7번 수행합니다.
둘 다 찾아야 하기 때문에 총 14번의 연산을 수행합니다.
만약 100개의 값이 주어지면 2x100번 연산을 수행합니다.
따라서 approach 2는 input size가 n일 때, 2n번 의 연산을 수행합니다.
위의 두 가지 접근법 중 어떤 것이 더 효율적일까요?
첫 번째 접근법은 크기가 2배 증가하면 시간은 4배 증가합니다.
두 번째 접근법은 크기가 2배 증가하면 시간이 2배 증가합니다.
두 번째 접근법이 첫 번째 접근법보다 효율적이라고 말할 수 있습니다.
approach 3) 정렬된 배열이라면 첫번째 값과 마지막 값 비교하기
배열이 정렬되어 있다는 가정이 추가되면
배열의 첫 번째 값은 언제나 최솟값, 마지막 값은 언제나 최댓값입니다.
주어진 값이 7개여도 100개여도 첫 번째 값을 아는데 1번, 마지막 값을 아는데 1번 연산을 수행합니다.
approach 3은 input size에 상관없이 언제나 2번의 연산을 수행합니다.
이 경우가 최고로 빠른 시간 복잡도를 가집니다.
2. Big-O Notation
알고리즘을 사용하는데 얼마나 많은 연산이 필요한지는 각 알고리즘마다 다릅니다.
Big-O 표기법을 사용해 시간복잡도를 표현할 수 있습니다.
Big-O 표기법은 input size가 충분히 크다고 하면 낮은 차수의 값, 상수는 큰 영향이 없다고 여기고 무시합니다. 따라서 2n을 O(n)으로 표현합니다.
위에서 살펴본 시간복잡도 외에 Big-O 표기법으로 표현하는 방법은 여러가지가 있습니다.
