● 문제 (Problem)
- 해답을 찾으려고 물어보는 질문
● 알고리즘 (Algorithm)
- 어떠한 문제를 해결하기 위해 정해 놓은 일련의 절차
○ 알고리즘의 조건
- 입력 : 알고리즘을 수행하는데 필요한 데이터가 외부에서 입력되어야 한다.
- 출력 : 알고리즘 수행 후 하나 이상의 결과를 출력해야 한다.
- 명확성 : 수행할 작업의 내용과 순서를 나타내는 알고리즘의 명령어는 명확하게 명세되어야 한다.
- 유한성 : 알고리즘은 수행 뒤에 반드시 종료되어야 한다.
- 효과성 : 알고리즘의 모든 명령어들은 기본적이며 실행이 가능해야한다.
○ 알고리즘의 순서
- 문제정의 → 알고리즘 설명 → 정확성 증명 → 성능 분석
- 문제정의(Problem Definition) : 해결하고자 하는 문제를 컴퓨터를 이용하여 풀 수 있도록 입력과 출력의 형태로 정의
- 알고리즘 설명(Algorithm Description) : 문제를 해결하기 위한 단계를 순서대로 나열
- 정확성 증명(Correctness Proof) : 항상 올바른 답을 내고, 정상적으로 종료되는지 증명
- 성능 분석(Performance Analysis) : 수행 시간이나 사용 공간에 대한 알고리즘의 성능을 비교하기 위해 분석
● 복잡도 (Complexity)
- 알고리즘의 성능을 객관적으로 평가하는 기준으로 시간복잡도와 공간복잡도로 나뉜다.
◎ 공간복잡도 (Space Complexity) = 고정 공간 + 가변 공간
- 알고리즘을 프로그램으로 실행하여 완료하기까지 필요한 총 저장 공간의 양
- 고정 공간 : 프로그램 크기나 입출력 횟수와는 상관없이 고정적으로 필요한 저장 공간으로 프로그램 저장 공간과 변수 및 상수를 저장하는 공간이다.
- 가변 공간 : 실행 과정에서 사용하는 자료와 변수를 저장하는 공간과 함수를 실행하는 데 관련 있는 정보를 저장하는 공간이다.
◎ 시간복잡도 (Time Complexity) = 컴파일 시간 + 실행 시간
- 알고리즘을 프로그램으로 실행하여 완료하기까지의 총 소요 시간
- 컴파일 시간 : 프로그램마다 거의 고정적인 시간 소요로 시간복잡도에서는 컴파일 시간을 의미 있는 시간으로 취급하지 않는다.
- 실행 시간 : 컴퓨터의 성능에 따라 달라질 수 있으므로 실제 실행 시간보다는 명령문의 실행 빈도수를 계산하여 추정한다.
# 명령문의 실행 빈도수 -> 단위 연산이 수행되는 횟수를 입력 크기에 대한 함수로 구하여 알고리즘의 성능을 분석한다.
◎ 시간복잡도 분석 (Time Complexity Analysis)
○ 일정 시간복잡도 분석 (Every-Case Time Complexity Analysis) : \(T(n)\)
- 입력 값에 상관없이 입력 크기에 따라 항상 단위 연산의 실행 횟수가 일정하다.
○ 최선 시간복잡도 분석 (Best-Case Time Complexity Analysis) : \(B(n)\)
- 입력 크기와 입력 값에 따라 단위 연산의 실행 횟수가 최소인 경우
○ 최악 시간복잡도 분석 (Worst-Case Time Complexity Analysis) : \(W(n)\)
- 입력 크기와 입력 값에 따라 단위 연산의 실행 횟수가 최대인 경우
○ 평균 시간복잡도 분석 (Average-Case Time Complexity Analysis) : \(A(n)\)
- 입력 크기와 입력 값에 따라 단위 연산의 실행 횟수가 평균인 경우
● 점근 표기법 (Asymptotic Notation)
○ Big O Notation(빅오 표기법)
\(g(n)\) ≤ \(c * f(n)\)
- 점근적인 상한 (Asymptotic Upper Bound)
- 함수의 상한을 나타내기 위한 표기법
- \(g(n)\)의 최고 차항이 \(f(n)\)의 최고 차항과 같거나 작아야한다.
- 즉, \(g(n)\)은 최악의 경우라도 \(f(n)\)과 같거나 빠르다.
○ Big Omega Notation(빅 오메가 표기법)
\(g(n)\) ≥ \(c * f(n)\)
- 점근적인 하한 (Asymptotic Lower Bound)
- 함수의 하한을 나타내기 위한 표기법
- \(g(n)\)의 최고 차항이 \(f(n)\)의 최고 차항과 같거나 커야한다.
- 즉, \(g(n)\)은 최선의 경우라도 \(f(n)\)과 같거나 느리다.
○ Big Theta Notation(빅 쎄타 표기법)
\(c * f(n)\) ≤ \(g(n)\) ≤ \(d * f(n)\)
- 점근적인 상한과 하한의 교집합 (Asymptotic Tight Bound)
- 함수의 상한과 하한이 같은 정확한 차수를 표현하기 위한 표기법
- \(g(n)\)의 최고 차항이 \(f(n)\)의 최고 차항과 같아야한다.
- 즉, \(g(n)\)은 아무리 좋아도 나빠도 \(f(n)\)의 범위 내에 있다.
댓글