알고리즘의 효율성 분석
명지대학교 컴퓨터공학과 이 충기 교수
주: 본 강의자료는 ‘알기 쉬운 알고리즘(양성봉 저)’ 교재에서 제공한 것을 수정한 것임.
지난 주 강의 내용
• 수학적 귀납법
• 기본 공식 증명
• 수열과 점화식
• 선형 점화식 해 구하기
이번 주 강의 내용
• 알고리즘의 효율성
• 시간 복잡도
• 알고리즘 복잡도 분석 방법
• 복잡도의 점근적 표기
• O(Big-Oh) 표기
• Ω(Big-Omega)-표기
• Θ(Theta)-표기
알고리즘의 세 가지 요소
• 효율적 알고리즘이 되기 위한 세 가지 요소
• ____의 효율성
• ____의 효율성
• ____의 효율성
• 프로그래머들이 프로그램을 개발할 때 항상
고민하는 내용
시간의 효율성
• 모든 알고리즘에서 가장 중요하게 생각 하는 요소
• 주어진 조건에서 문제를 해결하기 위해 가능한 한 빠른 시간 안에 가장 효율적 으로 해결책을 찾는 것이 진정한 알고 리즘
• 예: 게임 소프트웨어
• 알고리즘에 따라 작성된 프로그램이 컴 퓨터 메모리를 얼마나 사용하느냐?
• 대부분의 운영체제(OS)는 하나의 메모 리를 여러 개의 프로그램이 공유해서 사용
• 메모리를 효율적으로 관리하고 사용하는 것이 더욱 중요
공간의 효율성
코드의 효율성
• 개발자 입장과 컴퓨터 입장에서 보는 관점이 다름
• (개발자 입장) ____________ 코드가 좋은 코드
• 개발자가 시간이 지나서 다시 코드를 수정해야 하는 경우 쉽게 수정 할 수 있어야 한다.
• 다른 개발자가 코드를 볼 때에도 쉽게 이해할 수 있어야 한다.
• 프로그램의 소스 코드
• 다른 사람이 보고 이해하기 쉽도록 작성
• 이해하기가 쉽지 않은 코드는 주석(comment)을 이용하여 작성
• 변수나 함수를 작성할 때, 의미가 모호한 이름을 사용하지 말고 다른 사 람이 볼 때 쉽게 이해할 수 있는 이름으로 작성
• (컴퓨터 입장) 컴파일러와 하드웨어에 좀 더 최적화된 코드
알고리즘의 효율성 표현
• 알고리즘의 효율성은 알고리즘의 _______
또는 알고리즘이 수행하는 동안 사용되는 __________의 크기로 나타낼 수 있다.
• 이들을 각각 시간복잡도(time complexity), 공간복잡도(space complexity)라고 한다.
• 일반적으로 알고리즘들을 비교할 때에는 시
간복잡도가 주로 사용된다.
시간복잡도
• 시간복잡도는 알고리즘이 수행하는 _______
에 따라서 _______이 몇 번 수행되는 지를 함 수 로 표현
• 표현 척도
• 단위 연산(basic operation)
• 비교(comparison), 배정(assignment)
• 입력 크기(input size)
• 배열의 크기, 리스트(list)의 길이, 행렬에서 행과 열의 크 기, 트리(tree)에서 정점(node)와 연결선(edge)의 수
예: 시간복잡도 분석
• 10장의 숫자 카드들 중에서 최대
숫자 찾는 문제를 순차탐색으로 찾 는 경우에 숫자 비교가 단위 연산이 고, 총 비교 횟수는 __이다.
• n장의 카드가 있다면, ____번의 비
교 수행: 시간복잡도 = n-1
알고리즘 복잡도 분석 방법 (1)
• _____ 경우 분석(Every-case analysis)
• 입력크기에만 종속
• 입력 값과는 무관하게 결과 값은 항상 일정
• _____ 경우 분석(Worst-case analysis)
• 입력크기와 입력 값 모두에 종속
• 단위연산이 수행되는 횟수가 최대인 경우 선택
• _____ 경우 분석(Best-case analysis)
• 입력크기와 입력 값 모두에 종속
• 단위연산이 수행되는 횟수가 최소인 경우 선택
알고리즘 복잡도 분석 방법 (2)
• ____ 경우 분석(Average-case analysis)
• 입력크기와 입력 값 모두에 종속
• 모든 입력에 대해서 단위연산이 수행되는 기대치(평균)
• 각 입력에 대해서 확률 할당 가능
• 일반적으로 최악의 경우보다 계산이 복잡
최선 경우: 지하철역 도착 후 바로 승차
학교 통학 시간
소요 시간 = _____________________
최악 경우: 지하철 도착 후 놓치다 학교 통학 시간
소요 시간 = ______________________
평균 경우: 최악과 최선의 중간
학교 통학 시간
소요 시간 = ______________________
복잡도의 점근적 표기
•
복잡도의 점근적 표기
• 복잡도를 단순한 함수로 표현하기 위해 점근적 표 기 (Asymptotic Notation)를 사용한다.
• 입력 크기 n이 _____________복잡도를 간단히 표현하기 위해 사용하는 표기법은 다음과 같다:
• O(Big-Oh) -표기
• Ω(Big-Omega) -표기
• Θ(Theta) -표기
O(Big-Oh)-표기
•
O-표기는 복잡도의 ________
을 나타낸다.
•
복잡도가 f(n) = 2n
2- 8n + 3 이 라면, f(n)의 O-표기는 O(n
2) 이 다. 먼저 f(n)의 단순화된 표현 은 n
2이다.
•
단순화된 함수 n
2에 임의의 상
수 c를 곱한 cn
2이 n이 증가함
에 따라 f(n)의 상한이 된다. 단,
c>0.
• 복잡도 f(n) = O(g(n))을 그래프로 나타내면 아래와 같다.
• n이 증가함에 따라 O(g(n))이 점근적 상한이라는 것 (즉, cg(n)이 n0보다 큰 모든 정수 n에 대해서 항상 f(n)보다 크거 나 같다는 것)을 보여 준다. 단, c는 0보다 큰 상수이다.
O(Big-Oh)-표기
Ω(Big-Omega)-표기
• 복잡도의 ___________을 의미한다.
• f(n) = 2n
2- 8n + 3의 Ω-표기는 Ω(n
2)이다.
• f(n) = Ω(n
2)은 “n이 증가함에 따라 2n
2- 8n + 3이 cn
2보다 작을 수 없다”라는 의미이다.
이때 상수 c = 1로 놓으면 된다.
• O-표기 때와 마찬가지로, Ω-표기도 복잡도
다항식의 최고차항만 계수 없이 취하면 된
다.
• 복잡도 f(n) = Ω(g(n))을 그래프로 나타내면 아래와 같다.
• 즉, n이 증가함에 따라 Ω(g(n))이 점근적 하한이라는 것 (즉, cg(n) 이 n0보다 큰 모든 정수 n에 대해서 항상 f(n)보다 작거나 같다는 것)을 보여준다. 단, c는 0보다 큰 상수이다.
Ω(Big-Omega)-표기
Θ(Theta)-표기
• O-표기와 Ω-표기가 같은 경우에 사용한다.
• f(n) = 2n
2+ 10n + 3 = O(n
2) = Ω(n
2)이므로, f(n) = Θ(n
2)이다.
• “f(n)은 n이 증가함에 따라 n
2과 동일한 증 가율 을 가진다”라는 의미이다.
• f(n) ≠ Θ(n), f(n) ≠ Θ(nlogn), f(n) ≠ Θ(n
3),
f(n) ≠ Θ(2
n)이다.
• 복잡도 f(n) = Θ(g(n))을 그래프로 나타내면 아래와 같다.
• 즉, n0보다 큰 모든 정수 n에 대해서 f(n)은 c1 g(n) 보다 크거나 같고 c2 g(n) 보다 작거나 같다는 것을 보여준다. 단, c1 와 c2 는 0 보다 큰 상수이다.
Θ(Theta)-표기
자주 사용하는 O-표기
• O(1) 상수 시간 (Constant time)
• O(logn) 로그(대수) 시간 (Logarithmic time)
• O(n) 선형 시간 (Linear time)
• O(n logn) 로그 선형 시간 (Log-linear time)
• O(n2) 제곱 시간 (Quadratic time)
• O(n3) 세제곱 시간 (Cubic time)
• O(2n) 지수 시간 (Exponential time)
O-표기의 포함 관계
2n2+10n+3
n3+n2-10n+3
2n 5n+4 14, 1000
3logn+6
O(2n)
O(n3), O(n2)
O(logn)
O(1)
O(n)
O(nk)
복잡도 함수의 증가율
왜 효율적인 알고리즘이 필요한가?
• 10억 개의 숫자를 정렬하는데 PC에서 O(n2) 알고리즘은 300여년이 걸리는 반면에 O(n logn) 알고리즘은 5분 만에 정렬한다.
O(n2) 1,000 1백만 10억
PC < 1초 2시간 300년 슈퍼컴 < 1초 1초 1주일
O(nlogn) 1,000 1백만 10억 PC < 1초 <1초 5분 슈퍼컴 < 1초 <1초 <1초
바보 같은 예
•
좋은 예
•
알고리즘
•
빠른 알고리즘
•
• 효율적인 알고리즘은 슈퍼컴퓨터보다 더 큰 가치가 있다.
• 값 비싼 하드웨어의 기술 개발보다 효율적인 알고리즘 개 발이 훨씬 더 경제적이다.
결론
요약
• 알고리즘의 효율성은 주로 시간복잡도 (Time Complexity) 로 나타낼 수 있다.
• 시간복잡도는 알고리즘이 수행하는 기본적인 연산 횟수를 입력 크기에 대한 함수로 표현한다.
• 알고리즘의 복잡도 표현 방법:
• 최악 경우 분석 (worst case analysis)
• 평균 경우 분석 (average case analysis)
• 최선 경우 분석 (best case analysis)
• 점근적 표기 (Asymptotic Notation): 입력 크기 n이 무한대 로 커질 때의 복잡도를 간단히 표현하기 위해 사용하는 표 기법
