5-2

소팅-> selection : k등 찾기(nlogn) 쉬움(퀵소트이용)

 

Min(1) : 비교 최소 n-1번

 

Approximate Median 정의

- 대략적인 중간 원소

 

이걸로 찾아도됨 => logn 만족

비율의문제

(r=0.3)

0<r<1일때 rn등~(1-r)n등

30%(x) 40%(o) 30%==>selection O(n)가능,퀵소트최악 nlogn가능

 

아무거나꺼내면 40%

 

 

selection이 더어렵

 

A->S 풀이 : S -> A -> S순으로 둘이같이풀림

 

n/5개에서진짜 median찾기 ->

 

 

 

 

 

=> 결국머지소트보다느림, Selection전용

 

2등 : 토너먼트, n-1번, 개수는n개일때 높이는 logn, 1등한테 진놈들중 2등찾을수있음

Max

 

Median