Algorithm&Performance.md

Algorithm & Performance

알고리즘과 성능

알고리즘

• 유일한 단계를 통해 문제를 해결하기 위한 절차나 방법
• 주로 컴퓨터 용어로 쓰이며, 컴퓨터가 어떤 일을 수행하기 위한 단계적 방법을 말한다.ㄴ

표현 방법

• 의사코드
• 순서도

알고리즘 성능

좋은 알고리즘이란?

• 정확성
  • 얼마나 정확하게 동작하는가
• 작업량
  • 얼마나 적은 연산으로 원하는 결과를 얻어내는가
• 메모리 사용량
  • 얼마나 적은 메모리를 사용하는가
• 단순성
  • 얼마나 단순한가
• 최적성
  • 더 이상 개선할 여지없이 최적화 되었는가

시간 복잡도

연산의 작업량, 수행시간

• 최선의 경우 : 최선의 시나로오로 최소 이만한 시간이 걸림
  • 빅 오메가 표기법 사용
• 최악의 경우 : 최악의 시나리오로 아무리 오래 걸려도 이 시간보다 덜 걸림
  • 빅 오메가 표기법 사용
• 평균적인 경우 : 평균적인 시간을 나타냄
  • 빅 세타 표기법 사용

공간 복잡도

메모리 사용량

복잡도의 사용 목적

주어진 문제를 해결하기 위해 여러 개의 다양한 알고리즘이 가능하고 이러한 경우 알고리즘 별 성능을 분석할 필요가 있다.

빅-오(O) 표기법

• 시간 복잡도 함수 중에서 가장 큰 영향력을 주는 n에 대한 항만을 표시
• 계수는 생략하여 표시
• 예시 : O(n), O(n^2)