쉽게 배우는 알고리즘 1장 요약

1장. 알고리즘 설계와 분석의 기초

1. 몇가지 기초 사항들

알고리즘: 어떤 작업을 수행하기 위해 입력을 받아 원하는 출력을 만들어내는 과정을 기술한 것
알고리즘은 명확(이해하기 쉬움)하고 효율적(입력의 크기가 충분히 클때)이어야 한다.
입력이 충분히 큰 경우에 대한 분석: 점근적 분석(Asymptotic Analysis)
알고리즘은 대부분 소요시간이 관심의 대상이 된다 -> 최악의 경우와 평균적인 경우
알고리즘의 수행시간은 입력의 크기에 대해 시간이 어떤 비율로 소요되는지를 표현한다.
자기호출(재귀, recursion): 어떤 문제를 해결하는 과정에서 자신과 똑같지만 크기가 다른 문제를 발견하고 이들의 관계를 파악함으로써 문제 해결에 간명하게 접근하는 방식

2. 점근적 표기
a. Theta 표기법

알고리즘의 소요시간이 입력의 크기 n에 대해 Theta(n^2)이라면 대략 n^2에 비례하는 시간이 소요됨

b. Oh 표기법

알고리즘의 소요시간이 입력의 크기 n에 대해 Oh(n^2)라면 기껏해야 n^2에 비례하는 시간이 소요됨

c. Omega 표기법

알고리즘의 소요시간이 입력의 크기 n에 대해 Omega(n^2)이라면 적어도 n^2에 비례하는 시간이 소요됨

3. 점근적 표기의 엄밀한 정의

a. Oh 표기법

Oh(g(n)) = {f(n)|모든 n >= n0에 대하여 f(n) <= cg(n)인 양의 상수 c와 n0가 존재한다.}
엄밀한 상한 또는 여유있는 상한

b. Omega 표기법

Omega(g(n)) = {f(n)|모든 n>=n0에 대하여 cg(n)<=f(n)인 양의 상수 c와 n0가 존재한다.}
엄밀한 하한 또는 여유있는 하한

c. Theta 표기법

Oh(g(n))과 Omega(g(n))이 동시에 성립하는 모든 함수의 집합

d. Little Oh 표기법

o(g(n)) = {f(n)|n이 충분히 크면 모든 c>0에 대하여 f(n)<cg(n)이다}
함수의 증가율이 점근적 의미에서 어느 한계보다 더 작다는 것을 표현하고자 할 때 사용

e. Little Omega 표기법


w(g(n)) = {f(n)|n이 충분히 크면 모든 c>0에 대하여 cg(n)<f(n)이다}
함수의 증가율이 점근적 의미에서 어느 한계보다 더 크다는 것을 표현하고자 할 때 사용