<TIL> 13. 알고리즘

알고리즘은 어떠한 문제를 해결하려는 방법과 절차. 우리가 하려는 프로그래밍에 필요한 요소로 볼 수 있다.

알고리즘에 대한 조건
1. 입력: 외부에서 제공되는 자료
2. 출력: 적어도 2개 이상의 서로 다른 겨로가 출력
3. 명확성: 수행과정은 무엇을 하기 위한 것인지 명확하게 정의
4. 유한성: 알고리즘의 명령어 대로 수행했을 때 처리된 후 종료
4. 효율성: 시-공간적 효율성을 가져야 하며 명백하게 실행 가능

좋은 알고리즘이란?

• 복잡도(시간, 공간)
• 정확성: 입력에 대해서 일정 시간 내에 올바른 답을 산출하는거를 판단
• 작업량: 전체 알고리즘에서 수행되는 가장 중요한 연산들만으로 작업량 측정.
  해결하고자 하는 문제의 중요 연산이 여러 개인 경우에는 각각의 중요 연산들의 힘으로 간주하거나 중요 연산들에 가중치를 두어 계산
• 최적성: 작업을 수행하기 위한 알고리즘이 가장 접합한가?(가장 효율 적인가?)

시간복잡도

알고리즘이 특정 크기 입력에 대한 수행 시간을 의미
알고리즘이 수행하는 필요 연산 횟수

Big-O Notation(빅O표기법)

• 접근적 상한선(Asymptotic upper bound)
• 계수와 낮은 차수의 합을 제외시키는 방법
• 상수는 과감하게 삭제(모두 1이 된다)

공간복잡도
알고리즘이 특정 크기의 입력에 대한 메모리 소요량을 의미.
알고리즘이 수행되기 위해 필요한 저장공간(메모리)양

• 총 필요 저장공간
  * 고정공간(알고리즘 무관): 코드 저장공간, 상수
  • 가변공간(알고리즘 관련): 실행 중 동적으로 필요 공간