[알고리즘] Chapter 1. 알고리즘: 효율, 분석 그리고 차수

4학년 1학기 전공/알고리즘

[알고리즘] Chapter 1. 알고리즘: 효율, 분석 그리고 차수

시데브 2025. 4. 14. 19:35

경희대학교 한치근 교수님의 알고리즘 수업을 기반으로 정리한 글입니다.

1. 알고리즘

문제를 해결할 수 있는 잘 정의된(well defined) 유한(finite) 시간 내에 종료되는 계산적인(computational) 절차(prodcedure)
input -> output: 일련의 계산 절차

- 알고리즘과 Method의 차이

Algorithm: 유한 시간 내에 종료
Method: 유한 시간 내에 종료하는지 모름

문제의 표기 방법

문제: 답을 찾고자 던지는 질문
Parameter: 문제에서 특정 값이 주어지지 않은 변수 - 매개변수
Instance(입력): 파라미터에 특정 값을 지정한 것
Solution(출력): 주어진 사례에 관한 질문에 대한 답

수학적 귀납법(mathematical induction)

귀납 출발점(basis, base case): n = 0(또는 1)일 때, 주장이 사실임을 보임
귀납 가정(induction(inductive) hypothesis): 어떤 n에 대해서 주장이 사실임을 가정
귀납 절차(inductive step): n + 1에 대해서 주장이 사실임을 보임

-> n >= 2인 모든 n에 대해서 T(n) > 2^(n/2)

두 Fibonacci algorithm의 비교

2. 알고리즘의 분석(analysis)

공간복잡도(space(memory) complexity 분석)
- 입력 크기에 따라서 작업 공간(memory)이 얼마나 필요한지 결정하는 절차
- 표현 척도: input size
시간복잡도(time complexity) 분석
- 입력 크기에 따라서 단위연산이 몇 번 수행되는지 결정하는 절차
- 알고리즘이 수행되는 machine에 따라 문제 해결 시간이 달라짐
- 표현 척도: comparison, assignment

2.1. 분석 방법의 종류

Every-case analysis(모든 경우 분석)
- 입력 크기에만 종속, 입력 값과는 무관하게 결과 값이 항상 일정
Worst-case analysis(최악의 경우 분석)
- 입력 크기와 입력 값 모두에 종속
- 단위연산이 수행되는 횟수가 최대인 경우 선택
Average-case analysis(평균의 경우 분석)
- 입력 크기에 종속
- 모든 입력에 대해서 단위연산이 수행되는 기대치(평균)
- 각 입력에 대해서 확률 할당 가능
- 일반적으로 최악의 경우보다 계산이 복잡
Best-case analysis(최선의 경우 분석)
- 입력 크기와 입력 값 모두에 종속
- 단위연산이 수행되는 횟수가 최소인 경우 선택

- 배열 덧셈 시간복잡도 분석

- 교환 정렬 시간복잡도 분석

단위연산: 조건문(S[j]와 S[i]의 비교)
- every case
- j loop 수행 횟수: T(n) = n -1 + n -2 + ... + 1 = ((n-1)n)/2

단위연산: 교환 연산(exchange)
- worst case
- 조건문이 항상 true인 경우 -> W(n) = ((n-1)n)/2

- 행렬 곱셈 시간복잡도 분석

단위 연산: 가장 안쪽 for loop에 위치한 곱셈
- every case
- T(n) = n * n * n = n^3

- 순차 검색 시간복잡도 분석

단위 연산: 배열이 아이템과 키 x와 비교 연산(S[location] != x)
- worst case
  - x가 last item | x가 배열에 없는 경우 -> W(n) = n
- average case

best case
- x가 S[1]에 위치할 때, B(n) = 1

2.2. Discussion

complexity function: 음이 아닌 정수가 주어지면, 음이 아닌 실수를 내주는 함수 -> 정수 n을 시간으로 매핑!!
f(n) = n, lg n, 3n^2, ...

2.3. 정확도 분석

알고리즘이 의도한 대로 수행되는지 증명하는 절차
정확한 알고리즘: 어떠한 입려겡 대해서도 답을 출력하면서 멈추는 알고리즘
정확하지 않은 알고리즘: 어떤 입력에 대해서 멈추지 않거나, 틀린 답을 출력하면서 멈추는 알고리즘

3. 차수(order)

대표적인 복잡도 함수
- Θ(lg n)
- Θ(n): 1차 - linear
- Θ(nlg n)
- Θ(n^2): 2차 - quadratic
- Θ(n^3): 3차 - cubic
- Θ(2^n): 지수 - exponential
- Θ(n!)
- Θ(n^n)

3.1. 복잡도 함수의 증가율

3.2. Asymptotic(점근적) Behavior

n이 큰 수가 될 때의 함수 f(n)이 갖는 특성

3.3. 복잡도 함수 표기법

O() - big oh: aymptotic upper bound
o() - small oh: upper bound that is not asymptotically tight
Ω() - omega: aymtotic lower bound
ω() - small omega: lower bound that is not asymptotically tight
Θ() - theta: asymptotic tight bound

- big O notation

ex) 어떤 함수 g(n)이 O(n^2)에 속한다.
- n이 N보다 커진 시점에서 어떤 2차함수 cn^2보다는 반드시 작은 값을 가짐
- 함수 g(n)은 N보다 n이 큰 시점에, n^2보다는 반드시 성능이 좋다는 의미
- 시간 복잡도가 O(f(n)) -> 입력 크기 n에 대해서 알고리즘의 수행 시간이 아무리 늦어도 cf(n)은 된다는 의미
ex) n^2 + 10n이 O(n^2)에 속하는지?
- n >= 10인 모든 정수 n에 대해서 n^2 + 10n <= 2n^2 성립
- c = 2, N = 10에 대해서 n^2 + 10n이 O(n^2)에 속함

- Ω notation

ex) 함수 g(n)이 Ω(n^2)에 속한다.
- 정수 n이 N보다 커지는 순간부터, 함수 g(n)은 어떤 2차함수 cn^2보다는 반드시 큰 값을 가짐
ex) 어떤 알고리즘의 시간복잡도가 Ω(f(n))이라면,
- 이 알고리즘의 수행 시간은 cf(n)보다 절대로 더 빠를 수 없음

- Θ notation

- small O notation

complexity functions끼리의 관계를 나타내기 위한 notation

Big O와의 차이점
- Big O: 실수 c>0 중 하나만 성립해도 됨
- small o: 모든 실수 c>0에 대해서 성립해야 함

- ω notation

3.4. 차수의 주요 성질

3.5. 극한을 이용하여 차수를 구하는 방법

-> n이 충분히 커지면, n/2의 천장함수가 a^4보다 커짐

4. 알고리즘 복잡도와 컴퓨터 능력

알고리즘 복잡도가 cn일 때 t시간 동안
- 현재의 기계가 문제 크기 m개의 문제 해결
- 기계 처리 속도 2배 -> t시간 동안 2m개 문제 해결
알고리즘 복잡도가 cn^2일 때 t시간 동안
- 현재의 기계가 문제 크기 m개의 문제 해결
- 기계 처리 속도 4배 -> t시간 동안 2m개 문제 해결
알고리즘 복잡도가 c2^n일 때 t시간 동안
- 현재의 기계가 문제 크기 m개의 문제 해결
- 기계 처리 속도 2배 -> t시간 동안 m+1개 문제 해결
- 기계 처리 속도 100배 -> t시간 동안 m+6개 문제 해결
알고리즘 복잡도가 (A)일 때 t시간 동안
- 현재의 기계가 문제 크기 m개의 문제 해결
- 기계 처리 속도 (B)배 -> t시간 동안 (C)개 문제 해결

A	B	C
cn	2	2m
cn^2	4	2m
cn^3	8	2m
c2^n	2	m+1
c2^n	100	m + 6

-> t시간에 cm^3만큼의 연산이 가능

-> 기계 성능이 8배 되었으므로, t시간에 8cm^3 만큼 연산 가능

-> 증가된 문제 크기를 m'라 가정

-> c(m ')^3 = 8cm^3

-> m' = 2m

728x90