안녕

선택 문제란 키가 n개인 리스트에서 k번째로 큰 (혹은 k번째로 작은) 키를 찾는 것이다. 여기서 키는 정렬되어 있지 않은 리스트에 있다고 가정한다. 먼저 k = 1일 때, 우리는 가장 크거나, 가장 작은 키를 찾으면 된다. 그런 다음에, 최소키와 최대 키를 동시에 찾으면서 각각 따로 찾는 경우보다 더 적은 비교 횟수를 가짐을 볼 것이다. 마지막으로 k = 2일 때, 두 번째로 큰 값, 혹은 두 번째로 작은 값을 찾아볼 예정이다. 1. Finding the Largest Key problem : find the largest key in the array S of size n, indexed from 1 to n outputs : variable large, whose value is the larges..

문제를 푸는 알고리즘에 도전하는 방식은 두 가지가 있다. try to develop a more efficient algorithm for the problem try to prove that a more efficient algorithm is not possible 즉 알고리즘을 개선하던가, 아니면 더 효율적인 알고리즘은 만들 수 없다고 증명하던가 둘 중에 하나이다. 만약 더 효율적인 알고리즘을 만들 수 없다고 증명을 하면, 더 이상 알고리즘을 개선할 필요가 없다. 참고로 key의 comparison을 이용한 sorting algorithm은 nlgn보다 줄일 수 없다고 증명되었다. 1. Computational Complexity (계산 복잡도) 지금까지는 알고리즘의 복잡도를 계산했지만, 이 글에서..