[문제 해결 알고리즘] 알고리즘의 개요 및 복잡도

1. 알고리즘의 특성 및 최초의 알고리즘

 (1) 알고리즘의 특성

  - 알고리즘 : 문제를 해결하는 단계적인 절차, 방법

  - 입력이 주어지고 알고리즘을 수행한 결과인 해(또는 답)을 출력함

  - 정확성 : 주어진 입력에 대해 올바른 해를 주어야 함

  - 수행성 : 각 단계는 컴퓨터에서 수행 가능하여야 함

  - 유한성 : 일정한 시간 내에 종료되어야 함

  - 효율성 : 효율적일수록 그 가치가 높아짐

 (2) 최초의 알고리즘

  - 기원전 300년경 유클리드의 최대공약수 알고리즘

  - 최대 공약수 : 2개 이상의 자연수의 공약수 중 가장 큰 수

  - 2개의 자연수의 최대 공약수는 큰 수에서 작은 수를 뺀 수와 작은 수와의 최대 공약수와 같다는 성질을 이용

최대공약수  24, 14 > 24-14, 14 10, 14 > 14-10, 10 4, 10 > 10-4, 4 6, 4 > 6-4, 4 2, 4 > 4-2, 2 2, 2 > 2-2, 2 0, 2  최대 공약수 = 2

  - 유클리드 최대 공약수 알고리즘 Euclid(a, b)

  - 입력 : 정수 a, b (단, a >= b >= 0)

  - 출력 : 정수 c (a, b의 최대 공약수)

  - if b == 0 return a

  - return Euclid(b, a mod b)

2. 알고리즘의 표현 방법 및 효율성 표현

 (1) 알고리즘의 표현 방법

  - 일반적으로 알고리즘은 프로그래밍 언어와 유사한 의사 코드로 표현함

  - 알고리즘의 각 단계는 자연어로 서술할 수도 있으며, 컴퓨터 프로그래밍 언어로 표현할 필요는 없음

  - 예 ) 최대 숫자 찾기 알고리즘 : 플로 차트 / 의사 코드 / 자연어로 표현 가능

  - 자연어 표현 예시

   첫번째 숫자를 뽑고 기억해둠 > 다음 숫자를 뽑고 전 숫자와 비교함 > 큰 숫자만 기억함

   > 읽을 카드가 남아있는 경우 2단계로 감 > 머리속 숫자 출력

  - 의사 코드 찾기 표현 예시

   max = A[0] > for i = 1 to 9 > if (A]i] > max) max = A[i]  > return max

  - 플로 차트 ( □ : 동작, ◇ : 분기, ▷ 출력 )

 (2) 알고리즘의 효율성 표현

  - 알고리즘의 효율성은 다음으로 나타낼 수 있음

  - 시간 복잡도 : 알고리즘 수행 시 사용되는 수행 시간으로 나타낼 수 있음

  - 공간 복잡도 : 알고리즘 수행 시 사용되는 메모리 공간 크기로 나타낼 수 있음

  - 시간 복잡도 : 알고리즘이 수행하는 기본적인 연산 횟수를 입력 크기에 대한 함수로 표현

  - 10장의 숫자 카드 중에 최대 숫자 찾기

    ( 순차 탐색으로 찾는 경우에 숫자 비교가 기본 연산이고 총 비교 횟수는 9번임)

    ( n장의 카드가 있다면 n-1 의 비교 수행, n-1의 시간복잡도를 가짐)

  - 시간 복잡도 찾는 방법 : 최선, 평균, 최악의 경우를 찾는 3가지가 있지만 보통 최악의 경우로 계산

3. 복잡도의 점근적 표기

 (1) 복잡도 입력

  - 복잡도는 입력 크기에 대한 함수로 표기함

  - 이 함수는 주로 여러개의 항을 가지는 다항식임

  - 단순한 함수로 표기하기 위해 점근적 표기를 사용함

  - 입력 크기 n이 무한대로 커질 때의 복잡도를 간단하게 표현하기 위해 사용하는 표기법

 (2) Big-O 표기

  - 복잡도의 점근적 상한을 나타냄

  - 복잡도가 2n^2 -8n +3이라면 O-표기는 O(n^2)

 (3) Bin- Ω 표기 

  - 복잡도의 점근적 하한을 의미

  - 복잡도가 2n^2 -8n +3이라면 Ω-표기는 Ω (n) 혹은 Ω(1)

 (4) Big-Θ 표기

  - O 표기와  Ω 표기가 같은 경우에 사용

  - 정확할 때 사용

  - O와  Ω 사이의 값으로 표기

 (5) 효율적인 알고리즘의 필요성

  - 10억개의 숫자를 정렬할 때

  - O(N^2)의 경우 PC는 300년, 슈퍼컴 1주일

  - O(nlogn)의 경우 PC는 5분, 슈퍼컴 1초 미만

  - 효율적인 알고리즘은 슈퍼컴퓨터보다 더 큰 가치가 있음

  - 값 비싼 HW 기술 개발보다 효율적인 알고리즘 개발이 훨씬 더 경제적임