시간복잡도 썸네일형 리스트형 02. 알고리즘 분석 알고리즘의 효율성 분석을 위한 만능 공식은 없음. 대신, 몇몇 기본적인 방법들이 존재함. 알고리즘 분석은 대체로 안에서 바깥쪽으로 진행됨. 1. 순차적 규칙(Sequencing Rule) P1과 P2가 알고리즘의 두 부분이라고 한다면, 각각은 하나의 명령어이거나 복잡한 서브-알고리즘일 것임. 추가로, t1과 t2를 P1과 P2의 실행에 걸리는 시간이라고 했을 때 순차적 규칙에 의하면, P1과 P2의 실행에 거리는 시간은 단순히 t1+t2임. 최대 규칙(Maximum Rule)에 따르면, 이 시간은 θ( max{t1, t2} )임. 2. for 반복문 for i ← 1 to m, do P(i); 이 반복은 큰 알고리즘의 일부이고, 사이즈 n짜리 인스턴스에서 동작함. 2-1. P(i)에 걸리는 시간이 i와 .. 더보기 01. 알고리즘이란 * 문제와 해결방법 2 + 3 = ? 3 + 5 = ? 5 + 2 = ? ... 위와 같은 상황일 때, 알고리즘의 측면에서 문제는 한 개임. 일반적으로 말하는 문제를 여기선 인스턴스라고 함. 즉, 위에는 인스턴스가 3개인 것임. 해당 과목에서 "문제(Problem)"와 "인스턴스(Instance)"는 구분되어 사용됨에 유의할 것. - 한 문제는 많은(대체로 무수히 많은) 인스턴스를 가짐. 예를 들어, 두 양의 정수가 주어졌을때, 최대공약수(GCD, Greatest Common Divisor) 구하기라는 "문제"가 있을 때, 461,952 와 116,298 의 최대공약수를 구하기 (정답 = 18) 와 같은 "인스턴스"가 얼마든지 생성 될 수 있음. * 일반화 문제 P ) f : D -> R 인 f를 구해라.. 더보기 이전 1 다음
