시간복잡도2 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와 .. 2023. 10. 18. 01. 알고리즘이란 * 문제와 해결방법 2 + 3 = ? 3 + 5 = ? 5 + 2 = ? ... 위와 같은 상황일 때, 알고리즘의 측면에서 문제는 한 개임. 일반적으로 말하는 문제를 여기선 인스턴스라고 함. 즉, 위에는 인스턴스가 3개인 것임. 해당 과목에서 "문제(Problem)"와 "인스턴스(Instance)"는 구분되어 사용됨에 유의할 것. - 한 문제는 많은(대체로 무수히 많은) 인스턴스를 가짐. 예를 들어, 두 양의 정수가 주어졌을때, 최대공약수(GCD, Greatest Common Divisor) 구하기라는 "문제"가 있을 때, 461,952 와 116,298 의 최대공약수를 구하기 (정답 = 18) 와 같은 "인스턴스"가 얼마든지 생성 될 수 있음. * 일반화 문제 P ) f : D -> R 인 f를 구해라.. 2023. 10. 11. 이전 1 다음
