TIL-20-05-03

알고리즘의 기초

컴퓨터 알고리즘의 정의

컴퓨터 언어

• 컴퓨터와 대화하기 위해 사용하는 언어

컴퓨터 알고리즘

• 컴퓨터를 이용하여 주어진 문제를 효율적으로 풀기 위한 방법을 단계별로 기술해놓은 것
• 정렬알고리즘, 해시알고리즘, 최단거리알고리즘

컴퓨터 프로그램

컴퓨터가 특정 작업을 수행하기 위해 짜여진 명령의 순서

컴퓨터 알고리즘을 설명하기 위한 4단계

문제 정의

• 해결하고자 하는 문제는 무엇인가?
• 입력과 출력의 형태로 정의될 수 있는가?
• 컴퓨터가 수행할 수 있는 형태로 전환이 가능한가?

알고리즘 설명

• 컴퓨터가 수행해야 할 내용을 하나씩 차례대로 정의한 과정 (정확한 수치 설명)

정확성 증명

• 과정대로 수행하면 출력으로 항상 올바른 답을 내보내는가?
• 잘못된 답을 내보내는 경우는 없는가?
• 올바른 출력을 내보내고 정상적으로 종료되는가?

성능 분석

• 수행연산의 횟수를 비교하는 방식으로 성능을 분석. 횟수를 줄이는 게 좋은 알고리즘의 목표
• 수행 시간 / 사용 공간

컴퓨터 알고리즘의 수행 시간 분석

1) 가장 기본이 되는 함수를 판별하고, 함수를 몇 번 수행하는가를 성능 분석의 기본 2) 입력에 따라 수행 횟수 바뀌므로 입력 횟수는 n으로 정한다. 예를 들면 T(n)

성능 분석의 비교 대상

산술 연산

add, multiply, exponent, modular

데이터 입출력

copy, move, save, load

제어 연산

if, while, register

점근적 표기법

빅오 표기

오메가 표기

쎄타 표기