알고리즘

알고리즘이라는 용어는 어떠한 행동을 하기 위해서 만들어진 명령어들의 유한 집합입니다.

컴퓨터 프로그램은 정교한 알고리즘들의 집합이라 간주 가능합니다.

알고리즘 조건에 맞아야 알고리즘이라 부를 수 있습니다.

조건

1. 입력 : 외부에서 제공되는 자료가 0개 이상 있어야 합니다.
2. 출력 : 모든 입력에 하나의 출력이 발생되면 안 됩니다.
3. 명확성 : 수행 과정은 명확하고 모호하지 않은 명령어로 구성되어야 합니다.
4. 유한성 : 유한번의 명령어를 수행 후 유한 시간 내에 종료해야 합니다.
5. 효과성 : 모든 과정은 명백하게 실행(검증 가능) 한 것이어야 합니다.

좋은 알고리즘

• 정확성 : 적당한 입력에 대해서 유한 시간 내에 올바른 답을 산출하는 가를 판단
• 작업량 : 전체 알고리즘에서 수행되는 가장 중요한 연산들만으로 작업량을 측정한다.
• 기억 장소 사용량 : 수행에 필요한 저장공간의 최소 여부를 판단합니다.
• 최적성 : 작성한 알고리즘보다 더 적은 연산을 수행하는 알고리즘이 없어야 합니다.

알고리즘의 4단계

1. 문제 정의 : 해결하고자 하는 바를 input/output 나눠 정의합니다.
2. 알고리즘 설명 : 해결하기 위해 할 일들을 단계적으로 정의합니다.
3. 정확성 증명 : 알고리즘이 맞는지 수학적으로 증명합니다.
4. 성능 분석 : 시간, 공간 복잡도

시간 복잡도

• 입력 값의 변화에 따라 연산을 실행할 때 연산 횟수에 비해 시간이 얼마큼 걸리는가입니다.
• 효율적인 알고리즘을 구현한다는 것은 입력 값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘을 구성했다는 이야기입니다.
• T(n)과 같이 표기합니다.
• 이는 알고리즘이 n 크기의 입력량을 처리하는데 필요한 연산의 횟수를 말합니다.

공간 복잡도

• 프로그램을 실행시킨 후 완료하는 데 필요로 하는 자원 공간의 양을 말합니다.
• 총 공간 요구 = 고정 공간 요구 + 가변 공간 요구로 나타낼 수 있으며 수식은 S(P) = c +Sp(n)으로 표기합니다.
• O(n)과 같이 표기합니다.
• 이는 알고리즘이 n 크기의 입력량을 처리하는데 필요한 작업 기억 영역(메모리)의 양을 말합니다.

※ 고정 공간 : 입력, 출력의 횟수, 크기와 관계없는 공간의 요구(코드 저장 공간, 단순 변수, 고정 크기의 구조 변수, 상수)를 말합니다.

※ 가변 공간 : 해결하고자 하는 문제의 특정 인스턴스에 의존하는 크기를 가진 구조화 변수들을 위해서 필요로 하는 공간, 함수가 순환 호출을 할 경우 요구되는 추가 공간, 즉 동적으로 필요한 공간을 말합니다.