1. The Role of Algorithms in Computing

1.1. Algorithms

알고리즘입력을 받아 출력을 내는 잘 정의된 계산적 과정이다. 이는 잘 특징된 계산 문제로도 볼 수 있다. 예를 들어 정렬 문제를 정의하면 이렇다:

입력 : 숫자 n개의 순열, <a_1, …, a_n>

출력 : 입력 순열의 재배열 <a_1′, …, a_n’>으로, a_1′ ≤ a_2′ ≤ … ≤ a_n’ 을 만족함.

이 때 특정한 입력을 문제의 인스턴스라고 부른다. 알고리즘은 모든 입력 인스턴스에 대해 올바른 출력을 낼 때 정확한 알고리즘이라고 불린다. 정확한 알고리즘은 주어진 계산 문제를 푼다고 한다.

What kinds of problems are solved by algorithms?

Data Structures

자료 구조는 자료에 대한 접근과 수정을 용이하게 하기 위해 자료를 저장하고 구성하는 방식이다.

Technique

Hard problems

Parallelism

1.2. Algorithms as a technology

Efficiency

2장에서 두 가지의 정렬 알고리즘을 배울 것이다. 첫째 삽입 정렬은 n개의 항목을 정렬할 때 n^2에 비례하는 복잡도를, 둘째 병합 정렬은 n개의 항목을 정렬할 때 n log n에 비례하는 복잡도를 가진다.

Algorithms and other technologies

알고리즘은 기술과 같이 다뤄져야 한다.

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중