1. 알고리즘의 수행시간
가. 알고리즘을 통한 문제 해결
수학에서는 문제를 풀기 위해 정의나 정리들을 활용
컴퓨터에서는 문제 해결을 위해 알고리즘 이용
문제를 철저하게 분석한 후 알고리즘을 거쳐 프로그램 작성
나. 바람직한 알고리즘
1) 명확성
이해하기 쉽고 가능하면 간명하도록 해야 함.
지나친 기호적 표현은 오히려 명확성을 떨어뜨림.
명확성을 해치지 않으면 일반 언어의 사용도 무방
2) 효율성
같은 문제를 해결하는 서로 다른 알고리즘들의 수행 시간이 수백만 배 이상 차이날 수 있음.
다. 알고리즘 공부의 목적
알고리즘은 문제 해결 절차를 체계적으로 기술한 것
알고리즘 공부의 목적은 특정한 문제를 위한 알고리즘의 습득, 체계적으로 생각하는 훈련, 지적 추상화의 레벨 상승을 위함.
같은 문제에서도 효율이 아주 큰 차이가 나는 다양한 알고리즘이 존재
알고리즘을 학습하는 과정에서 얻을 수 있는 여러 가지 기법과 생각하는 방법도 중요
라. 알고리즘 분석의 필요성
바람직한 알고리즘은 명확하고 효율적이어야 함.
알고리즘을 설계하고 나면 이 알고리즘이 자원을 얼마나 소모하는지 분석해야 함.
자원은 소요 시간, 메모리, 통신 대역 등
자원의 가장 중심 대상은 소요 시간
시간의 분석은 최악의 경우와 평균적인 경우에 대한 분석이 대표적
시간 분석을 통해 알고리즘이 입력의 크기에 따라 어느 정도 시간이 필요한지 미리 예상 가능하며, 주어진 자원(시간)으로 작업이 완료 가능한지 알 수 있음.
마. 알고리즘의 수행 시간
알고리즘의 수행 시간은 입력의 크기에 대해 시간이 어떤 비율로 소요되는지로 표현됨.
1) 입력의 크기
정렬의 경우 정렬하고자 하는 개체의 수
도시 간의 최단 거리를 구하는 경우, 계산에 관여되는 도시와 도시 간 간선(도로)의 수
계승을 구하는 경우에는 계승치를 구하고자 하는 자연수의 크기
2) 입력값 n에 따른 알고리즘 수행 시간
\( O(1) \: < \: O( \log_{2}{n}) \: < \: O(n) \: < \: O(n\log_{2}{n}) \: < \: O(n^{2}) \: < \: O(n^{3}) \: < \: O(2^{n}) \)
\(O(1)\) 상수 시간(Constant time)
\(O(\log{n})\) 로그 시간(Logarithmic time)
\(O(n)\) 선형 시간(Linear time)
\(O(n\log{n})\) 로그 선형 시간(Log-linear time)
\(O(n^{2})\) 제곱 시간(Quadratic time)
\(O(n^{3})\) 세제곱 시간(Cubic time)
\(O(2^{n})\) 지수 시간(Exponential time)
https://ko.wikipedia.org/wiki/시간_복잡도
시간 복잡도 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 러닝 타임은 여기로 연결됩니다. 매체의 재생·상영 시간에 대해서는 러닝 타임 (매체) 문서를 참고하십시오. 계산 복잡도 이론에서 시간 복잡도는 문제를 해결
ko.wikipedia.org
3) 알고리즘의 수행시간을 좌우하는 기준
for 루프의 반복 횟수, 특정한 행이 수행되는 횟수, 함수의 호출횟수 등
4) 재귀적(Recursive) 알고리즘
재귀 = 자기호출
재귀적 사고는 해법을 알고 그것을 반복적으로 적용시킴.
어떤 문제 안에 크기만 다를 뿐 성격이 똑같은 작은 문제들이 포함되어 있는 것
병렬화 개념은 하나의 일을 나누어 동시에 병렬로 처리
팩토리얼, 수열의 점화식, 피보나치, 병합 정렬 등
2. 알고리즘의 효율성 분석
가. 알고리즘의 분석
알고리즘의 자원 사용량을 분석
자원이란 실행 시간, 메모리, 저장장치, 통신 등
여기서는 실행 시간의 분석에 대해서 다룸.
나. 알고리즘의 복잡도
여러 알고리즘 중 처리 시간이나 차지하는 메모리 용량이 작은 알고리즘이 프로그램 효율성도 높음.
알고리즘을 어떤 식으로 작성하느냐에 따라 실행되는 시간과 공간이 다르며 이것을 알고리즘의 복잡도라고 함.
1) 성능 측정
실제 구현 후 실행시켜 시간을 확인
구현해야 하므로 잘 안 씀.
2) 성능 분석
구현하기 전 입력 개수에 따른 실행 횟수 계산
다. 시간 복잡도
실행 시간을 측정하는 대신 연산의 실행 횟수를 분석
연산의 실행 횟수는 입력 데이터의 크기(n)에 관한 함수로 표현
최악의 경우, 평균의 경우, 최선의 경우를 분석
3. 점근적 표기
가. 점근적 분석
입력 크기가 작은 문제는 알고리즘의 효율성이 중요하지 않지만 입력 크기가 충분히 큰 문제는 비효율적인 알고리즘은 치명적
입력 크기 n이 무한대로 커질 때의 복잡도를 간단히 표현하기 위해 사용하는 표기법
유일한 분석법도 아니고 가장 좋은 분석법도 아니지만 가장 간단하고, 알고리즘의 실행환경에 비의존적이기 때문에 광범위하게 사용됨.
\(O\) (Big-O) 표기
\(\Omega\) (Big-Omega) 표기
\(\Theta\) (Big-Theta) 표기
https://ko.wikipedia.org/wiki/점근_표기법
점근 표기법 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 점근 표기법(漸近 表記法, 영어: asymptotic notation)은 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수론과 해석학의 방법이다. 알고리즘의 복잡도를
ko.wikipedia.org
나. Big-O 표기법
복잡도의 점근적 상한을 나타냄.
정의
\(f(n)\)과 \(g(n)\)이 주어졌을 때, 모든 \(n \geq n_{0}\)에 대하여 \(f(n) \leq cg(n)\)을 만족하는 상수 \(c\)와 \(n_{0}\)가 존재하면 \(f(n) = O(g(n))\)이다.
다. Big-Omega 표기법
복잡도의 점근적 하한을 나타냄.
정의
\(f(n)\)과 \(g(n)\)이 주어졌을 때, 모든 \(n \geq n_{0}\)에 대하여 \(f(n) \geq cg(n)\)을 만족하는 상수 \(c\)와 \(n_{0}\)가 존재하면 \(f(n) = \Omega (g(n))\)이다.
라. Big-Theta 표기법
복잡도의 상한과 하한이 동시에 적용되는 경우를 나타냄.
Big-O 표기와 Big-Omega 표기가 같은 경우에 사용
정의
\(f(n)\)과 \(g(n)\)이 주어졌을 때, 모든 \(n \geq n_{0}\)에 대하여 \(c_{1}g(n) \leq f(n) \leq c_{2}g(n) \)을 만족하는 상수 \(c_{1}\), \(c_{2}\)와 \(n_{0}\)가 존재하면 \(f(n) = \Theta (g(n))\)이다.
마. 효율적인 알고리즘
10억 개의 숫자를 정렬하는데 \(O(n^{2})\) 알고리즘은 300여 년이 걸리는 반면에 \(O(n \log {n} )\) 알고리즘은 5분 만에 정렬함.
효율적인 알고리즘은 슈퍼컴퓨터 개발보다 더 큰 가치가 있음.
값 비싼 하드웨어의 기술 개발보다 효율적인 알고리즘 개발이 훨씬 더 경제적
