컴퓨터는 주어진 문제(problem)를 해결하기 위해 여러 산술연산 및 논리연산을 수행하는 다목적 장치이다. 컴퓨터 알고리즘은 이러한 컴퓨터를 이용하여 문제를 풀기위한 방법을 과정이나 절차를 이용하여 만들어 놓은 것이다.

• 컴퓨터가 문제를 풀려면 무엇을 실행해야 하는지를 정의해야한다.
• 정의 후에는 컴퓨터가 할 수 있는 일로 변환시켜 주어야 한다.
  • 컴퓨터가 할 수 있는 가장 작은 기본 작업의 형태로 만들고 이를 순차적으로 나열해준다.

컴퓨터 알고리즘의 4가지 단계

• 문제 정의 (Program Definition)
  문제를 컴퓨터가 이해하고 풀 수 있는 형태로 바꾸어 준다.

• 알고리즘 설명 (algorithm Description)
  문제를 풀기 위해 수행해야하는 작업을 순서대로 나열해 놓은 것

• 정확성 증명 (Correctness Proof)
  주어진 알고리즘을 수행했을 때 문제를 풀 수 있는지를 증명하는 과정이다.

  • 부분 정확성 : 문제의 해답을 정확히 찾는가?
  • 전체 정확성 : 문제의 해답을 찾을 뿐만 아니라 정상적으로 알고리즘이 종료하는가?

• 성능평가 (Performance Analysis)
  알고리즘이 어떤 문제를 풀기 위해서 필요한 시간이나 공간 혹은 그 외의 자원들이 얼마나 되는지를 비교하기 위해 사용한다.

  ​

  ​

B. 알고리즘의 성능분석

점근적 표기법 (Asymptotic Notation)

알고리즘이 주어진 데이터의 크기를 기준으로 수행시간 혹은 사용공간이 얼마나 되는지를 객관적으로 비교할 수 있는 기준을 제시해 준다.

• O(빅오) 표기법
  점근적 상한선을 의미한다. 즉 알고리즘의 최악의 성능을 표시해준다. 아무리 나빠도 비교하는 함수와 같거나 좋다는 뜻이다.
  ‘아무리 최악의 상황이라도 이정도의 성능을 보장할 수 있다’ 는 것을 증명하기 위해 가장 많이 쓰이는 방법이다.

• Ω(오메가) 표기법
  점근적 하한선을 의미한다. 즉 알고리즘의 최고의 성능을 표시해준다. 아무리 좋아도 비교하는 함수와 같거나 나쁘다는 뜻이다.

• θ(세타) 표기법
  점근적 상한선과 점근적 하한선의 교집합을 의미한다. 주어진 함수가 아무리 좋아지거나 나빠져도 비교하는 함수의 범위안에 있다는 뜻이다.

성능비교의 대상

• 산술 연산 (사칙연산)

• 데이터 이동 연산 (copy, move, save, load)

• 제어 연산 (if, while ,register)

  ​
  * 빅오 표기법 참고 Blog