2.2 알고리즘의 분석 알고리즘의 분석은 그 알고리즘을 실행하는 데 필요한 자원을 예측하는 것을 의미한다. 메모리, 통신 대역, 하드웨어 등 대부분은 계산 시간을 의미한다. 이 책에서의 가정 알고리즘은 단일 프로세서와 랜덤 접근 기계(RAM, random-access machine) 모델로 가정 : 명령어는 동시X, 하나씩 실행 산술 연산, 데이터 이동연산, 제어 연산 등 : 상수 시간 RAM 모델의 데이터형 : 정수(integer)와 부동소수(floating point) 각 워드 크기에 제한을 가정 : 입력 크기가 n인 입력을 다룰 때 정수는 상수 c>= 1에 대해 clg2비트로 표현된다고 가정(워드는 상수로 처리하므로 너무 크면 안된다.) ...
2.1 삽입정렬 정렬문제 입력 : n개 수들의 수열 $$ <a_1, a_2, …, a_n> $$ 출력 : $$ a’_1 <= a’_2 <= … <= a’_n $$ 을 만족하는 입력 수열의 순열(재배치) $$ <a’_1,a’_2, …, a’_n> $$ 정렬하고자 하는 숫자를 키라고 한다. 의사코드와 “실제” 프로그램 코드의 차이는, 의사 코드에서는 알고리즘을 가장 분명하고 간결하게 서술할 수 있다면 어떤 표현 방법을 사용해도 좋음. 영어, 한글 문장등이 들어갈 수 도 있음. 데이터 추상화, 모듈화, 오류처리 등의 소프트웨어 공학 관점의 문제를 고려하지 않음. ...
1.1 알고리즘 알고리즘 어떤 값이나 값의 집합을 입력으로 받아 또 다른 값이나 값의 집합을 출력하는 잘 정의된 계산 절차 어떤 입력을 어떤 출력으로 변환하는 일련의 계산과정 잘 정의된 계산 문제를 풀기 위한 도구 정렬 문제 입력 : n개 수들의 수열 $$ <a_1,a_2, …, a_n> $$ 출력 : $$ a^{’}_1≤a^{’}_2≤ …≤a^{’}_n $$ 을 만족하는 입력 수열의 순열(재배치) $$ <a^{’}_1, a^{’}_2, …, a^{’}_n> $$ ex) <31, 41, 59, 26, 41, 58>이 입력 수열로 주어지면 정렬 알고리즘은 수열 <26, 31, 41, 41, 58, 59>를 출력한다. -> 입력수열 : 정렬 문제의 사례 ...
1.2 기술로서의 알고리즘 컴퓨터는 상당히 빠를 수 있지만 ‘무한히’ 빠를수는 없다. 메모리도 매우 저렴할 수 있지만 비용이 ’전혀‘ 들지 않을 수는 없다. 효율성 동일한 문제 해결을 위한 알고리즘이 효율성 면에서 극적으로 다를 수 있다. 하드웨어, 소프트웨어로 인한 차이보다 더 심각할 수 있다. ex) 삽입 정렬 : n개의 값 정렬위해 $$ c_1n^2 $$ 에 비례하는 시간 걸림(c_1은 n에 독립인 상수). 즉, n^2에 비례함 병합 정렬 : $$ c_2nlog_2n $$ 의 시간 걸림(c2는 n에 독립인 또 다른 상수). 즉, nlog_2(n) 상수는 입력 크기 n에 비해 수행시간에 영향을 훨씬 작게 준다. ...