[알고리즘 기초] 컴퓨터 알고리즘에 대해

Study/Algorithm

ChoiSenn 2022. 3. 10. 18:14

문제를 해결하는 단계적 절차 또는 방법이다. 주어지는 문제는 컴퓨터를 이용하여 해결할 수 있어야 한다. 알고리즘에는 입력이 주어지고, 알고리즘은 수행한 결과인 해(또는 답)를 출력한다.

정확성 : 알고리즘은 주어진 입력에 대해 올바른 해를 주어야 한다.

수행성 : 알고리즘의 각 단계는 컴퓨터에서 수행 가능해야 한다.

유한성 : 알고리즘은 일정한 시간 내에 종료되어야 한다.

효율성 : 알고리즘은 효율적일수록 그 가치가 높아진다.

알고리즘의 형태는 단계별 절차이다. 알고리즘의 단계는 보통 말로 서술할 수 있으며, 프로그래밍 언어로만 표현할 필요는 없다. 일반적으로 알고리즘은 프로그래밍 언어와 유사한 의사코드(pseudo code)로 표현한다.

알고리즘의 효율성은 수행시간(시간복잡도) 또는 알고리즘이 수행하는 동안 사용되는 메모리 공간의 크기(공간복잡도)로 나타낼 수 있다.

일반적으로 알고리즘 비교 시에는 시간복잡도가 주로 사용된다.

알고리즘이 실행되는 동안에 사용된 기본적인 연산 횟수를 입력 크기의 함수로 나타낸다.

기본연산이란 데이터 간의 크기 비교, 데이터 읽기 및 갱신, 숫자 계산 등 단순한 연산을 의미한다.

최악경우분석 : '어떤 입력이 주어지더라도 알고리즘의 수행시간이 얼마 이상은 넘지 않는다'라는 상한의 의미

평균경우분석 : 입력의 확률 분포를 가정하여 분석하는데, 일반적으로 균등분포를 가정한다.

최선경우분석 : 가장 빠른 수행시간을 분석하며, 최적의 알고리즘을 찾는 데 활용된다.

상각분석 : 일련의 연산을 수행하여 총 연산 횟수를 합하고 이를 연산횟수로 나누어 수행시간을 분석한다.

일반적으로 알고리즘의 수행시간은 최악경우분석으로 표현한다.

시간복잡도는 입력 크기에 대한 함수로 표기한다. 이 함수는 주로 여러 개의 항을 가지는 다항식이다. 이를 입력의 크기에 대한 함수로 표현하기 위해 점근적 표기를 사용한다.

점근적 표기는 입력 크기 n이 무한대로 커질 때의 복잡도를 간단히 표현하기 위해 사용하는 표기법이다.

빅-O 표기, 빅오메가 표기, 세타 표기가 있다.