[알고리즘] 알고리즘 분석

복잡도분석

---

복잡도 분석의 일반적인 방식

[ 알고리즘의 시간 복잡도 분석 ]

입력 크기에 대해 기본 연산이 몇 번 수행되는지 결정
• 전체 실행 시간(작업량): 기본 연산(basic operation)이 수행되는 횟수와 비례
• 알고리즘의 실행 시간: 입력 크기(input size)가 증가함에 따라 증가
=> 알고리즘의 효율성은 기본 연산이 입력 크기의 함수로 몇 번 수행되는지를 분석하는 것으로 결정됨

[ 복잡도 분석을 위해서 ]

• 1단계: 입력 크기 결정하기
• 2단계: 기본 연산 선택하기

(1) 입력크기(input size) 결정하기
• 대부분의 알고리즘에서는 입력 크기를 정의할 수 있는 합리적인 방법을 찾을 수 있음
• 입력 크기 ≠ 입력의 크기 자체
참고 예를 들어, n=13일 경우, 이진수 표현은 1101이며, 입력 크기 = 4비트(lg(n)+1)
• 알고리즘의 효율성을 종속적인 요인에 따라 분석하지 말 것 (입력크기는 독립적)
❌ CPU 사이클 수는 알고리즘의 성능을 결정하는 기준이 될 수 없음
❌ 모든 명령어를 개별적으로 계산하는 것은 부적절: 언어 / 개발자의 코드 스타일에 따라 실행되는 명령어 수가 달라짐

(2) 기본연산 선택하기
• 알고리즘 내에서 특정 명령어 또는 명령어 그룹을 선택할 것
예 순차/이진탐색 알고리즘에서 비교 연산(comparison instruction)이 반복적으로 수행됨
• 알고리즘이 어떻게 구현되었는지에 대한 세부 사항은 고려하지 않으며, 기본 연산이 최대한 효율적으로 구현된다고 가정
• 두 개의 기본 연산을 고려해야 할 수도 있음
예 키 값을 비교하면서 정렬하는 알고리즘에서는 비교연산과 할당연산을 기본 연산으로 고려 가능
❌ 기본 연산의 반복 횟수를 증가시키는 단순한 루프 제어 명령어는 포함하지 말 것
예 루프를 제어하는 인덱스를 증가시키고 비교하는 연산은 고려 대상에서 제외
• 기본 연산의 횟수를 셀 때, 반복문의 한 번 실행을 기본 연산의 한 번 수행으로 간주할 수도 있음

시간복잡도 분석

---

시간복잡도 분석 표기

[ T(n) ]

Every-Case Time Complexity
• 용법 1) 구체적인 실행 시간 함수, 특정 입력에 대한 수행시간
• 용법 2) 일반적인 전체 수행 시간 함수, 알고리즘의 전체 실행 시간

용법 2	의미	설명
W(n)	Worst-Case Time Complexity	최악의 경우 시간 복잡도, 알고리즘이 가장 비효율적일 때 입력 크기가 n일 때 모든 가능한 입력에 대해 알고리즘이 기본 연산을 수행하는 최대 횟수
A(n)	Average-Case Time Complexity	평균적인 경우의 시간 복잡도 입력 크기가 n일 때 모든 가능한 입력에 대해 알고리즘이 기본 연산을 수행하는 평균 횟수 크기가 n인 가능한 모든 입력에 확률을 할당해야 함
B(n)	Best-Case Time Complexity	최선의 경우 시간 복잡도, 알고리즘이 가장 효율적일 때 입력 크기가 n일 때 모든 가능한 입력에 대해 알고리즘이 기본 연산을 수행하는 최소 횟수

참고: 용법 2인 경우에만
• T(n)에 W(n), A(n), B(n)이 포함
• A(n) = T(n), W(n) = T(n)

[ Every-Case Time Complexity 예제]

배열 요소 더하기(Add Array Members)
• 기본 연산: 배열의 각 항목을 합(sum)에 추가하는 연산
• 입력 크기: n (배열 내 항목의 개수)
• 배열 내 숫자의 값과 관계없이, for 루프를 n번 반복
• 기본 연산: 항상 n번 수행
• 시간 복잡도: T(n)=n

교환 정렬(Exchange Sort)
• 기본 연산: S[j]와 S[i] 비교 (비교연산과 할당연산 고려가능, 여기서는 비교연산)
• 입력 크기: n (정렬할 항목의 개수)
for 루프의 반복 횟수 분석

외부 루프(for-i 루프)는 n−1번 반복
내부 루프(for-j 루프)는 첫 번째 반복에서 n−1번 실행
두 번째 반복에서 n−2번 실행,…, 마지막 반복에서는 1번 실행
• for-j 루프의 총 실행 횟수는 다음과 같이 계산됨:
T(n)=(n−1)+(n−2)+(n−3)+⋯+1 => T(n)=(n−1)⋅n/2(등차수열의 합 공식)
• 시간 복잡도: T(n^2)

행렬 곱셈(Matrix Multiplication)

가장 안쪽의 for 루프에서 실행되는 유일한 명령은 곱셈과 덧셈입니다. 이 알고리즘은 덧셈보다 곱셈을 더 적게 수행하도록 구현할 수 있다. 따라서 우리는 곱셈 연산만을 기본 연산으로 간주한다

• 기본 연산: 가장 안쪽 for 루프에서 곱셈 연산 수행
• 입력 크기: n, 행과 열의 개수
설명 for-i 루프에서 n번, for-j 루프에서 n번, 각 for-k 루프에서도 n번 실행
• 시간복잡도: T(n)=n×n×n=n^3

[ 순차탐색(Sequential Search)으로 최선, 최악, 평균 시간 복잡도 알아보기 ]
순차탐색(Sequential Search) 예제
• 기본 연산: 배열 내 요소를 x와 비교
• 입력 크기: n, 배열 내 요소 개수

시간복잡도	설명
W(n) = n	x가 배열의 마지막 요소이거나 배열 내 존재하지 않는 경우로 기본 연산이 최대 n번 실행
B(n) = 1	x가 첫 번째 요소일 경우 한 번만 실행됨
A(n)	• x가 배열 내 존재한다고 가정하면, 배열 내 모든 위치에 있을 확률이 동일함 • x가 k번째 슬롯에 위치할 확률은 $1/n$, $x$를 찾기 위해 기본 연산이 $k$번 실행됨 • 시간 복잡도: $A(n) = \sum_{k=1}^{n} \left( k \times \frac{1}{n} \right) = \frac{1}{n} \sum_{k=1}^{n} k = \frac{1}{n} \times \frac{n(n+1)}{2} = \frac{n+1}{2}$
A(n)	x가 배열에 없을 수도 있는 경우 x가 배열 내 존재할 확률은 p, 없을 확률은 1-p, x가 k번째 슬롯에 있을 확률 p/n x가 존재하면 k번 실행, 존재하지 않으면 n번 실행 시간 복잡도: $A(n) = \sum_{k=1}^{n} \left( k \times \frac{p}{n} \right) + n(1 - p)$ $= \frac{p}{n} \times \frac{n(n+1)}{2} + n(1 - p) = n\left(1 - \frac{p}{2} \right) + \frac{p}{2}$
A(n)	특수한 경우: • p = 1이면, $A(n) = (n + 1)/2$ • 1/2이면, $A(n) = \frac{3n}{4} + \frac{1}{4}$ 즉 평균적으로 배열의 3/4을 탐색

복잡도 함수

(1) 일반적인 개념 복잡도 함수 (complexity function)

양의 정수를 비음수 실수로 매핑하는 임의의 함수 가 될 수 있음

특정 알고리즘의 시간 복잡도 또는 메모리 복잡도를 지칭하지 않는 경우, 일반적으로 f(n)이나 g(n) 같은 표준 함수 표기법을 사용

`예`
f(n)=n
f(n)=n^2 
f(n)=logn
f(n)=3n^2 +4n

기타 명령어 (Other Instructions)

(1) 오버헤드 명령어 (Overhead instructions)

반복문 실행 전 초기화 명령어 등
이러한 명령어의 실행 횟수는 입력 크기와 무관함

(2) 제어 명령어 (Control instructions)

루프를 제어하기 위해 인덱스를 증가시키는 명령어 등
이러한 명령어의 실행 횟수는 입력 크기와 함께 증가함

비교 예제 두 개의 알고리즘이 동일한 문제를 해결한다고 가정하자

첫 번째 알고리즘: 시간 복잡도 $O(n)$
두 번째 알고리즘: 시간 복잡도 $O(n^2)$

• 첫 번째 알고리즘이 더 효율적으로 보이지만, 특정 컴퓨터에서는 기본 연산을 처리(제어명령을 포함한 전체 실행시간)하는 속도 차이에 따라 실행 시간이 달라질 수 있음

ex 첫번째 알고리즘이 기본연산을 1회 수행하는 데 두 번째 알고리즘보다 1000배 오래 걸린다면?
• 두 알고리즘 모두 오버헤드 명령 시간은 무시할 정도로 작다고 가정
• 첫 번째 알고리즘의 총 실행 시간: n × 1,000t, 두 번째 알고리즘의 총 실행 시간: n² × t
• 해결할 부등식: $n×1000t < n^2×t$

정확성 분석 (Analysis of Correctness)

요구 사항 (Requirement):
알고리즘이 실제로 의도한 대로 동작하는지를 증명함으로써, 우리는 그 알고리즘의 정당성(correctness)을 분석할 수 있음