optimality2 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. Analysis of the Algorithm 3 Worst-Case Complexity Average Complexity - Pr(I): input I가 발생할 확률 - t(I)는 알고리즘 분석으로 결정할 수 있지만, Pr(I)는 분석적으로 계산 불가능 Optimality - 알고리즘 복잡도 2021. 3. 24. 이전 1 다음
