알고리즘18 Array search알고리즘의 Optimality n개 원소를 갖는 배열 E와 정수 K가 주어진다. K=E[index]인 인덱스를 찾고, 없으면 -1을 리턴하라. 1. A: unsorted Array일 때, 순차적 탐색 W(n) = n (Worst case) A(n) = q[(n+1)/2]+(1-q)n (Average case. q:탐색에 성공할 확률) unsorted일 때 F(n)=n 이므로 알고리즘 A는 optimal 2. B: 오름차순 정렬된 배열일 때, 순차적 탐색 W(n) = n A(n) = q[(n+1)/2]+(1-q)n 배열이 정렬되었다는 정보를 이용하지 않음. optimal X 3. C: 오름차순 정렬된 배열일 때, 순차적 탐색하다가 K보다 큰 원소를 만나면 -1 리턴 (찾는 원소가 없다) W(n) = n+1 => n Asucc(n) = .. 2021. 3. 24. Classifying Functions - Big oh, theta, omega Classifying Functions 점근 증가율, 점근 순서. 상수나 small input은 무시하고 비교한다. Ω(g): big omega. lower bound. 최소 g만큼 빠르게 증가하는 함수 ex) Ω(n)이면 n+10, n^3+3 모두 해당됨 Ω(g): big oh. upper bound. g보다 증가율이 빠르지 않은 함수 ex) Ω(n^2)이면 n^2+7, 3n+10 모두 해당됨 Θ(g): big theta. g와 같은 비율로 증가하는 함수. Ω(g)∩Ω(g) Little oh, little omega: big oh, big omega에서 증가율이 같은 경우는 제외한 것 Big oh, theta, omega의 특성 1. Transitive(전이성): f∈O(g)이고 g∈O(h)면 f∈O(.. 2021. 3. 24. Analysis of the Algorithm 3 Worst-Case Complexity Average Complexity - Pr(I): input I가 발생할 확률 - t(I)는 알고리즘 분석으로 결정할 수 있지만, Pr(I)는 분석적으로 계산 불가능 Optimality - 알고리즘 복잡도 2021. 3. 24. Analysis of the Algorithm 2 Proof (증명법 1. Counterexample - 반례 2. Contraposition - 대우 3. Contradiction - 모순, 귀류: 결론을 부정하고 모순임을 보임 4. Mathematical Induction - 수학적 귀납법 : i가 초기값에 대해 참, i가 k에 대해 참이라고 가정할 때 k+1일 때도 참임을 증명 Analyzing Algorithms and Problems - Correctness 증명하기 1. if the precondition(input data) are satisfied, ex) 정수정렬문제면 인풋이 정수인지 2. then the postcondition(output data) will be true, 3. whe the algorithm terminates A.. 2021. 3. 24. Analysis of the Algorithm 1 Analysis of the Algorithm 실험적 분석: 구현 필수, 실험하지 않은 인풋에 대한 결과를 알 수 없음, 비교할 때 환경이 동일해야 함 이론적 분석: 구현 전 파악, 수행시간을 n함수로 정의, 모든 인풋에 대해 고려, 환경과 상관없는 평가 가능 Worst-Case Analysis - W(n): 최대 basic operation 수를 n으로 표현한 함수. - Analysis Tool 1. Mathematics - Series : the sum of a sequence 2. Logic A => B ㄱA v B ㄱ(A ^ B) ㄱA v ㄱB 드모르간의 법칙 ㄱ(A v B) ㄱA ^ ㄱ 2021. 3. 24. 알고리즘의 과정 - 알고리즘이란 : a detailed step-by-step method for solving a problem (유한 시간 내에) by using a computer. - 과정 1. Problem - 문제 정의: input/ouput 2. Strategy - 전략 세우기 3. Algorithm - 알고리즘 서술: Input / Output / Step(Speecification) 4. Analysis - 알고리즘 분석 - Correctness : 어떤 입력에 대해서도 가능함을 보인다. - Time & Space(Storage) - Optimality : 최적성. problem complexity = algorithm complexity일 때 최적. 5. Implementation - 구현 6. Ver.. 2021. 3. 23. 이전 1 2 3 다음
