1.1. 알고리즘의 역할

1.1.1 알고리즘

연습문제

1. "정렬" 또는 "컨벡스 헐 찾기" 계산 문제 중 하나를 골라 이런 문제가 발생하는 현실의 예를 제시하라

   • 데이터를 시간순으로 보여줘야 할때?

2. 현실에서 속도 외에 효율성을 평가할 만한 다른 척도로 무엇이 있는지 제시하라

   • CPU / 메모리 사용의 효율성

3. 예전에 본 적이 있는 자료구조 중 하나를 골라 그것의 장점과 한계를 각각 논하라

   • 트리 -> 검색이 빠르나 삽입과 삭제가 복잡

4. 앞서 설명한 최단 경로 문제와 순회 판매원 문제는 어떻게 비슷한가. 그리고 어떻게 다른가?

   • 최단시간에 어디로 간다는 문제에서 비슷하지만 최단 경로 문제와 다르게 외판원 문제는 모든 곳을 빠짐없이 방문해야 한다.

5. 현실의 문제 중 최적해만 의미가 있는 문제를 제사하라. 반대로 최적은 아니지만 "근접한" 해를 구해도 충분한 문제를 제시하라

   1. 암호화된 데이터를 복호화 하는 알고리즘

   2. 웹페이지 검색

1.1.2 기술로써의 알고리즘

알고리즘에 대한 별다른 지식 없이도 최신 컴퓨터 기술을 통해 어떤 일을 할 수 있을지도 모른다. 하지만 알고리즘에 대한 훌룡한 배경 지식을 쌓으면 훨씬 더 많은 일을 할 수 있을것이다.

연습문제

1. 응용 프로그램 수준에서 알고리즘이 필요한 프로그램의 예를 들라. 그리고 이용된 알고리즘의 기능에 대해 논하라

   • 택시 배차 알고리즘, 사용자에로부터 최단 거리에 있는 택시를 배차한다.

2. 동일한 기계에서 삽입 정렬과 병합 정렬의 구현 결과를 비교한다고 가정하자. n개의 입력에 대해 삽입 정렬은 8n^2 번을, 병합 정렬은 64 n lg n 번을 계선하고 각각 종료한다. n의 앖이 얼마일 때 삽입 정렬이 병합정렬보다 빠를까?

   1. 8n^2 < 64n log2(n)

   2. n < 8 log2(n)

   3. n < 8 log n / log 2

   4. n < 44

   5. 43개일때까진 삽입정렬이 병합정렬보다 효율적임

3. 동일한 기계에서 수행시간이 100n^2 인 알고리즘이 수행시간이 2^n 알고리즘보다 빨라지는 n의 최솟값은 얼마인가?

   1. n^2<2^(n - 2)/25

   2. n > 14.3247

   3. 15