주어진 문제를 유한한 시간 내에 해결하는 단계적 절차
데이터를 조직하고 접근하는 체계적 방식
알고리즘 + 데이터 구조
알고리즘을 설명하기 위한 고급 언어
자연어 문장보다 더 구조적, 프로그래밍 언어보다 덜 상세
Alg arrayMax(Arr, n)
input array Arr of n integers
output maximun element of Arr
1. currenMax ← A[0]
2. for i ← 1 to n-1
if(A[i] > currentMax)
currentMax ← A[i]
3. return currentMax
<if문>
if(exp)
statement
elseif(exp)
statement
else
statement
<for문>
for var ← exp to exp
statement
for var ← exp downto exp
statement
<foreach문>
for each var ∈ exp
statement
<while문>
while(exp)
statement
<do-while문>
do
statement
while(exp)
Alg methodname(arg) 정의
something
return exp 반환
methodname(arg) 호출
{ 주석내용 }
← 치환
= < ≤ > ≥ 관계 연산자
& || ! 논리 연산자
s₁ n² 수학적 표현 (쳠자 등)
- 무제한의 메모리 셀을 갖는 하나의 CPU
- 메모리 셀은 순번으로 나열되고, 임의의 수/문자 데이터를 저장
- 임의접근기계가 어떤 셀에 접근할 때 항상 상수시간 소요
3-1. 임의접근기계가 원시작업을 실행 시 항상 상수시간 소요
의사코드로 표현 가능한, 알고리즘에 의해 수행되는 기본적 계산
(e.g.) EXP, ASS, IND, CAL, RET
의사코드를 조사하여 알고리즘이 실행하는 원시작업의 최대 개수를 입력크기의 함수 형태로 결정할 수 있다.
Alg something(n)
input integer n
output integer m
1. m←0 {ASS / 1}
2. for i←0 to n-1 {ASS, EXP / 2+n}
m←i {ASS / n}
3. return m {RET / 1}
{원시작업 갯수 합 : 1 + 2+n + n + 1 = 2n+3}
원시작업 수 : 5n+3
T(n) : 알고리즘 T에 대한 최악의 실행시간
a : 가장 빠른 원시작업의 실행 시간
b : 가장 느린 원시작업의 실행 시간
실행시간의 증가율은 어떤 알고리즘의 고유한 속성이다.
나열된 순서로 입력크기에 따른 실행시간의 증가율이 크다
함수형태 | 함수이름 | n=100일 때 값 |
---|---|---|
c | 상수함수 | 1 |
logn | 로그함수 | 7 |
log2n | 로그제곱함수 | 49 |
n | 선형함수 | 102 |
nlogn | 로그선형함수 | 7*102 |
n2 | 2차함수 | 104 |
n3 | 3차함수 | 106 |
2n | 지수함수 | 1030 |
주어진 두 개의 함수 f(n)과 g(n)에 관해,
만약 모든 정수 n≥n0에 대해 f(n)≤c • g(n)가 성립하는
실수의 상수 c>0 및 정수의 상수 n0≥1가 존재하면,
"f(n)=O(g(n))"이라고 말한다.
함수의 증가율의 상한을 나타낸다.
f(n) = O(g(n))
→ f(n)의 증가율이 g(n)의 증가율을 넘지 않는다.
→ 점근적으로 f(n)≤g(n) 이다.
(e.g.)
f(n) = 7n-2
--> f(n) = O(n)이라 두면
--> 7n-2 ≤ cn 은 c=7, n0=1에 대해 만족
주어진 두 개의 함수 f(n)과 g(n)에 관해,
만약 모든 정수 n≥n0에 대해 f(n)≥c • g(n)가 성립하는
실수의 상수 c>0 및 정수의 상수 n0≥1가 존재하면,
"f(n)=Ω(g(n))"이라고 말한다.
함수의 증가율의 하한을 나타낸다.
f(n) = Ω(g(n))
→ f(n)의 증가율은 g(n)의 증가율을 넘는다.
→ 점근적으로 f(n)≥g(n) 이다.
주어진 두 개의 함수 f(n)과 g(n)에 관해,
만약 모든 정수 n≥n0에 대해 c'•g(n)≤f(n)≤c''•g(n)가 성립하는
실수의 상수 c'>0, c''>0 및 정수의 상수 n0≥1가 존재하면,
"f(n)=Θ(g(n))"이라고 말한다.
함수의 증가율의 상/하한을 모두 나타낸다. ( = 동일함수를 나타낸다.)
f(n) = Θ(g(n))
→ f(n) = O(g(n)) = Ω(g(n))
→ 점근적으로 f(n) = g(n) 이다.