ch 2. efficiency and analysis

• 알고리즘의 학습 목표
• Design
• 알고리즘 설계 기법 학습
• Analysis
• 알고리즘을 분석하여 시간/공간 복잡도 구함
• Comutational Complexity
• 문제에 대한 하한을 결정
  

• 알고리즘
• (General) Step-by-step procedure for producing the solution to each instance
• 유한한 단계를 통해서 문제에 대한 답을 구함
• cf. 연산은 효율성(+간결성)/명확성/종결성/입출력

• 알고리즘의 표기
• 자연어
• 복잡한 문제를 쓰기 어렵고, 알고리즘 이해가 어려우며, 프로그래밍 언어로 바꾸기 어려움
• 프로그래밍언어
• 자연어의 단점은 극복되었으나, 특정 언어에 종속
• 의사코드 (pseudo-code)
• 알고리즘은 대부분 의사코드로 표현
• 직접 실행할 수 있는 프로그래밍 언어는 아니지만, 실제 프로그램과 가깝게 계산과정을 나타낼 수 있음

• 차수 (Order)
• 참고 링크 : https://en.wikipedia.org/wiki/Time_complexity
•  Big O Notation
• 점근적 상한 (Asymptotic upper bound)
• Omega Notation
• 점근적 하한 (Asymptotic lower bound)