개요

알고리즘

주어진 문제를 유한한 시간 내에 해결하는 단계적 절차

데이터 구조

데이터를 조직하고 접근하는 체계적 방식

프로그램

알고리즘 + 데이터 구조

의사코드

알고리즘을 설명하기 위한 고급 언어

자연어 문장보다 더 구조적, 프로그래밍 언어보다 덜 상세

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² 		수학적 표현 (쳠자 등)

임의접근기계 모델

1. 무제한의 메모리 셀을 갖는 하나의 CPU
2. 메모리 셀은 순번으로 나열되고, 임의의 수/문자 데이터를 저장
3. 임의접근기계가 어떤 셀에 접근할 때 항상 상수시간 소요
   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}

실행시간

특징

• 실행시간은 입력크기와 함께 성장
• 최악실행시간의 분석이 평균실행시간 대비 용이하고 결정적

실험적 방법을 통한 실행시간 추정

• 과정
  1. 알고리즘을 구현하는 프로그램을 작성
  2. 다양한 입력을 사용하여 실행 + System Call로 실행시간 측정
  3. 도표형태로 결과 작성 ( e.g. : X축 입력크기 / Y축 실행시간 )
• 한계
  • 모든 입력에 대한 결과를 반영 불가
  • 여러 알고리즘을 비교시 동일한 HW, SW환경 필요
  • 알고리즘을 완전한 프로그램으로 구현 어려움

이론적 방법을 통한 실행시간 추정

• 특징 ← 실험적 방법의 한계 해결
  • 모든 입력가능성 고려
  • hw, sw 무관
  • 의사코드로 표현된 알고리즘 사용
• 실행시간 추정
  • 가정
    원시작업 수 : 5n+3
T(n) : 알고리즘 T에 대한 최악의 실행시간
a : 가장 빠른 원시작업의 실행 시간
b : 가장 느린 원시작업의 실행 시간
  • 실행시간 T(n)
    a(5n+3) ≤ T(n) ≤ b(5n+3)

실행시간의 증가율

실행시간의 증가율은 어떤 알고리즘의 고유한 속성이다.
나열된 순서로 입력크기에 따른 실행시간의 증가율이 크다

Big-Oh 표기법

주어진 두 개의 함수 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에 대해 만족

Big-Omega 표기법

주어진 두 개의 함수 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) 이다.

Big-Theta 표기법

주어진 두 개의 함수 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) 이다.