Computer Algorithms by Yang-Sae Moon Page 1
알고리즘 : 효율 , 분석 , 차수
Homework #2 (1/2)
1.리스트에서 복수 개의 가장 작은 수 찾는 알고리즘
(1) n 개의 수로 구성된 리스트에서 m 개의 가장 작은 수를 찾는 알고리 즘을
작성하시오 .
(2) 작성한 알고리즘에 대해 , (a) 단위 연산을 정의하고 , (b) 시간 복잡도를 계산하시오 . (n >> m)
2.이진검색이 순차검색보다 빠르므로 , 숫자들의 배열을 정렬한 후 이진검 색을 수행하는 검색방법 ( 이를 A 라 하자 ) 을 설계하였다 . 이 A 가 순차 검색보다 좋지 않음을 시간 복잡도 측면에서 설명하시오 .
Computer Algorithms by Yang-Sae Moon Page 2
알고리즘 : 효율 , 분석 , 차수
Homework #2 (2/2)
3.차수의 성질을 사용하여 다음을 증명하시오 . (1)
(2) (3)
(4) loga n (logb n), where b > 1, a > 1.
4 5 3 2 5
5 logn n4n 6n 2n n 7 ( )n
2 3
1 ( )
n
i i n
2 2
3y 8 logy y ( )y
