1. 알고리즘의 분석
알고리즘 분석에는 두 가지 방법이 있습니다.
- The correctness of an algorithm
- The efficiency of an algorithm
- how efficiency the algorithm solves a problem in terms of either time or space
이때, 정확도 분석은 학부생의 레벨이 아니고 대학원생의 레벨입니다.
그리고 수학적 증명이 필요하기 때문에 학부생 레벨에서는 패스하겠습니다.
그러면 이제 알고리즘의 효율성 분석이 있습니다.
이때, 시간과 공간 측면에서 분석을 해야합니다.
하지만 공간은 그렇게 중요한 부분이 아닙니다. 메모리는 부족하면 언제든지 추가 구매하면 되니까요.
하지만 시간은 매우 중요합니다. 공간을 많이 먹어도 시간이 적은 알고리즘이 더 좋은 알고리즘입니다.
이때, 시간은 그러면 어떻게 측정할까요?
시간은 cpu의 실제 작동 시간을 측정하지 않습니다. 다음과 같은 이유입니다.
- 특정 컴퓨터와 무관해야합니다.
- 특정 언어와 무관해야합니다.
- 알고리즘의 복잡한 디테일과 무관해야합니다.
따라서 측정 방법은 단위 연산이 수행되는 횟수를 입력의 크기에 대한 함수로 구하여 효율성을 분석합니다.
이를 복잡도 분석(Complexity Analysis)라고 합니다.
2. Basic Operation
알고리즘의 효율성을 증명하기 위한 전형적인 기법입니다.
일반적으로, input size에 따라 basic operation가 얼마나 많이 수행되느냐로 증명합니다.
이때, basic operation은 저희가 정하기 나름입니다. 앞선 search에서도 비교를 기본 연산으로 했습니다.
하지만 basic operation을 아무렇게나 정하지는 마세요. 합리적인 이유에 의해서 정해야합니다.
bubble sort를 예를 들겠습니다.
def bubble_sort(n): # 오름차순으로 정렬
for i in range(0, n):
for j in range(i + 1, n):
if data[i] > data[j]:
data[i], data[j] = data[j], data[i]이때, 기본 연산은 뭐로 해야할까요?
swap하는 명령어일까요?? 아닙니다. data[i] > data[j] <-- 이 비교 명령어가 기본 연산이 되어야합니다.
왜일까요?
이유는 간단합니다. 어떤 리스트냐에 따라 swap 명령어를 실행하는 횟수가 다르기 때문입니다.
n이 같더라도, 입력받는 리스트의 원소에 따라 swap 실행 횟수가 달라집니다.
하지만 딱 n에 종속적이게 변하는 값이 있죠. 바로 비교 명령어입니다.
이처럼 basic operation은 아무렇게 정하는 것이 아니고, 합리적이게 정해야합니다.
알고리즘에 의해 수행된 작업은 저희가 정한 basic operation의 연산 횟수에 대략적으로 비례해야합니다!
위의 bubble_sort 알고리즘은
(n-1) + (n-2) + (n-3) + ... + 1이므로 basic operation의 연산 횟수는 1/2(n^2-n)이 되겠습니다!
3. 효율성 증명을 위한 복잡도 종류
T(n)
시간에 대한 복잡도, 즉 time complexity는 basic operation이 input size에 따라 얼마나 많은 연산을 했는지를 결정합니다.
이때, 입력의 값에 상관없이 입력 크기(input size, n)에 대해서 실행횟수가 일정하다면 every-case time complexity라고 합니다.
일정 시간복잡도라고 하고, 기호는 T(n)이라고 합니다.
배열을 모두 더하는 함수는 배열 안의 원소의 값과 상관없이 항상 n번 수행하죠. 그러면 T(n) = n입니다.
또한, Bubble Sort도 입력 값과 상관없이 일단 비교부터 합니다. 유일한 변수는 배열의 길이입니다.
하지만, sequential search는 말이 다르죠.
입력 값이 배열의 처음이면 1번 실행하고, 입력 값이 배열에 없으면 n번 실행합니다.
이렇게 입력 크기뿐만 아니라, 입력 값에 따라서도 시간 복잡도가 달라질 수 있는데요.
이때, 우리는 이 경우에 대해서 세 가지 측정 방법이 있습니다.
- best-case time complexity
- worst-case time complexity
- average-time complexity
W(n)
W(n)은 worst-case time complexity입니다. 최악의 상황을 상정하는 겁니다.
Sequential Search에서 최악의 상황은 뭐였죠? 입력 값이 배열에 없는 상황입니다.
이때, 우리는 W(n) = n 이라고 합니다.
아무리 느려도 이 시간보다는 빨리 된다는 뜻입니다.
B(n)
B(n)은 best-case time complexity입니다. 최고의 상황을 상정합니다.
Sequential Search에서 최고의 상황은 바로 입력 값이 배열의 맨 첫 번째에 있을 때입니다.
이때, B(n) = 1입니다.
A(n)
A(n)은 Average-case time complexity입니다. 평균적인 상황입니다.
어떤 입력 값이 들어왔을 때, 이 n을 구하는 평균 횟수를 계산합니다.
만약에 n = 5인 배열이 있다고 가정하고, 입력 값 x가 배열 안에 있다고 가정합시다.
이때, 모든 횟수를 세봅시다.
1, 2, 3, 4, 5가 되겠죠? x가 첫 번째, 두 번째, .... , 마지막에 있을 때의 횟수입니다.
이때 평균 계산 횟수는 3번입니다.
따라서 Sequential Search의 A(n)은 1/2(n+1)이 됩니다!
하지만 입력 값 x가 배열 안에 없다면 어떡할까요?
x가 배열 안에 있을 확률이 p일 때, 없을 확률은 1-p입니다.
이때 A(n)은 n(1 - p/2) + p/2입니다.
만약 p = 1이면 A(n)은 1/2(N+1)이 되지만, p = 1/2라면 a(n)은 3n/4 + 1/4입니다. 평균적으로 배열의 3/4를 검색한다는 뜻입니다.
이렇게 입력 값에 상관없이 입력 크기에 좌우되는 것이 T(n)(평균 시간 복잡도)이고,
입력 값과 입력 크기에 T(n)이 좌우될 때, 저희는 W(n), B(n), A(n)을 사용합니다.
평균적으로는 W(n)과 A(n)을 더 많이 사용합니다.
이때, 평균의 오류에 빠지지 않도록 해야합니다.
책의 말을 그대로 인용하겠습니다.
핵발전소 감시 시스템이 있고,
모든 반응 속도가 3초 부근인 것과 대부분 반응 속도가 1초이지만, 가끔 60초기 때문에 평균 반응이 3초인 것과는 엄연한 차이가 있습니다.
이때는 A(n)보다는 W(n)을 더 중요하게 여겨야합니다.
마지막으로 또 다른 오류를 말씀드리겠습니다.
1번 알고리즘의 T(n) = n
2번 알고리즘의 T(n) = n^2 일때,
당연히 1번 알고리즘이 더 효율적입니다.
이제 다른 알고리즘을 비교해보겠습니다.
3번 알고리즘의 T(n) = 100n
4번 알고리즘의 T(n) = 0.01n^2 일때,
어떤 알고리즘이 더 효율적일까요??
n > 10,000일때, 3번 알고리즘이 비로소 더 효율적이게 됩니다.
이렇게 어떤 알고리즘이 다른 알고리즘보다 어느 시점부터 빠른지 정확히 결정하기가 어려운 경우가 많습니다.;
하지만 저희는 n < 10,000일때를 가정하지 말고, 궁극적으로 무엇이 더 빠른지가 더 중요합니다.
시간 복잡도에 대한 설명은 끝났고, 이제 남은건 공간 복잡도입니다.
저희가 지금까지 계산했던 모든 사항이 공간 복잡도에도 적용할 수 있습니다.
필요한 경우 공간 복잡도 분석도 다룰 예정입니다.
4. 요약
오늘은 알고리즘의 분석의 종류와 기본 연산, 그리고 복잡도 종류에 대해 알아봤습니다.
알고리즘은 정확도와 효율성을 분석할 수 있고, 저희 레벨에서는 효율성을 분석합니다.
효율성을 분석하기 위해서 실제 시간은 너무나 의존적인 부분이 많기 때문에 기본 연산의 연산 횟수로 알고리즘의 효율을 비교합니다.
이때 효율을 비교하기 위해서 쓰는 복잡도 종류가 총 4가지가 있습니다.
T(n) : 입력 값과 상관 없이 입력 크기에만 의존적일 때
W(n) : 입력 값과 입력 크기에 의존적일 때, 최악의 상황
B(n) : 입력 값과 입력 크기에 의존적일 때, 최고의 상황
A(n) : 입력 값과 입력 크기에 의존적일 때, 평균의 상황
마지막으로 두 가지 실수할 수 있는 오류에 대해 말씀 드렸습니다.
첫 번째는 평균의 오류입니다. 평균은 곧 모든 상황이 평균이라는 것이 아니라는 걸 명심하셔야합니다.
두 번째는 입력 크기를 제한했을 때의 오류입니다. 저희는 모든 알고리즘을 특정 n의 범위에서 측정하는 것이 아닌 궁극적으로 어떤 알고리즘이 더 효율적인지를 측정합니다.
다음 시간에는 시간 복잡도의 차수에 대해서 설명드리겠습니다.
감사합니다.
지적 환영합니다.
출처 : 알고리즘 기초, 수업 강의