[Algorithm] 알고리즘 설계와 분석의 기초

알고리즘 설계와 분석의 기초

알고리즘이란

문제를 해결하기 위한 단계적 절차를 말한다. 어떤 작업을 수행하기 위해 입력을 받아 원하는 출력을 만들어내는 과정을 기술한 것이다.

 

점근적 분석

점근적 분석이란 입력이 충분히 큰 경우에 대한 분석을 말한다. 컴퓨터는 빠른 처리 능력을 가지므로 입력의 크기가 작을땐 속도의 차이가 뚜렷하지 않다. 하지만, 충분히 큰 입력에서는 알고리즘의 효율성에 따라 수행 시간이 크게 차이가 날 수 있다.

좋은 알고리즘 = 성능이 좋은 = 효율적인 = 같은 시간에서 더 빠른 알고리즘이다.

알고리즘 표현법

• 순서도를 이용한 표현
  • 여러 종류의 상자와 상자를 이어 주는 화살표를 이용해서 명령 순서를 표현
  • 간단한 알고리즘은 쉽게 표현할 수 있지만, 복잡한 알고리즘은 표현하기 어려운 경우가 많다.
  • <순서도 예시>

  • 

• 의사 코드를 이용한 표현
  • 프로그래밍언어 + 자연어를 사용한 표기법
  • 프로그램 코드를 직접 코딩하는 것 보다 좀 더 명확하게 정립하는 데 도움이 되고 코드에 설명을 달지 않아도 이해하는 데 무리가 없다.
• 프로그램 코드로 표현
  • 실제로 사용하는 프로그래밍 언어의 코드로 바로 작성 가능

알고리즘은 자료구조의 확장이다!
자료구조는 생각의 전개를 위해 필요한 기본적인 도구이다.알고리즘을 설계하는 것은 자료구조에서 출발한다. 어떤 문제를 해결하기 위해서는 자료를 어떻게해야 효율적으로 표현, 조직, 저장 관리할지 알아야하기 때문이다.

몇가지 기초 사항들

1. 알고리즘 분석의 필요성 :
   • 알고리즘을 설계한 후 설계한 알고리즘이 자원을 얼마나 소모하는지 분석해야한다. 여기서 자원은 소요 시간, 메모리, 통신 대역 등이 되는데 대부분 '소요 시간'이 중요한 관심 대상이다.
   • 사용하고자 하는 알고리즘의 소요 시간이 입력의 크기에 어떤 비율로 비례하는지 안다면 주어진 시간에 요구하는 작업을 완료할 수 있을지 대략 짐작할 수 있다.
2. 알고리즘의 수행 시간
   • 알고리즘의 수행 시간 : 입력의 크기에 대해 시간이 어떤 비율로 소요되는지 표현.
3. 재귀(자기호출)과 귀납적 사고
   • 자기호출을 이용하는 알고리즘에서 자기호출을 제외한 나머지 부분은 대부분 크키가 다른 문제간의 관계를 반영하는 것이다.
   • 자기호출은 어떤 문제를 해결하는 과정에서 자신과 똑같지만 크기가 다른 문제를 발견하고 이들의 관계를 파악함으로써 문제 해결에 간명하게 접근하는 방식이다. 수학적 귀납법은 자신보다 작은 문제에 대해 결론이 옳음을 가정하고 자신과 이 작은 문제의 관계를 통해서 자신에게도 결론이 옳음을 보이는것이다. 따라서 귀납적 사고라는 것은 성격이 같지만 크기가 다른 "관계"를 파악하는 것이라는 점에서 자기호출과 관계가 깊다.

 

점근적 표기

알고리즘의 수행시간은 항상 입력의 크기가 충분히 클 때를 분석하는 점근적 분석을 한다.

n이 작을 때는 차이가 그리 크지 않지만 n이 커짐에 따라 차이는 극적으로 벌어진다.

알고리즘을 분석하려고 입력의 크기로 무엇을 잡을지는 대부분 명확하다. 예를 들어, 여러 수를 크기 순으로 정렬하는 알고리즘이라면 정렬하고자 하는 수의 개수가 입력의 크기가된다.
그래프 알고리즘에서는 대부분 정점의 개수가 간선의 개수 둘을 입력의 크기로 사용한다.

• 가정 :
  앞으로 알고리즘의 소요 시간이나 자원의 소모량을 표현하는 함수는 양의 값을 갖는다고 가정한다. 음의 시간은 의미가 없기 때문이다.
• 표기법은 집합으로 정의되며, ∈ 대신 = 를 쓴다.

1. Θ - 표기법
   • Θ(f(n))은 최고차항의 차수가 f(n)과 일치하는 모든 함수의 집합이다.
   • 예를들어, Θ(n^2)은 n^2, 3n^2-50, 7n^2+16 등을 포함한다.
2. O - 표기법O-표기는 함수의 점근적 상한을 나타낸다.
   • O(f(n))은 점근적 증가율이 f(n)을 넘지 않는 모든 함수의 집합이다.
     O(f(n))은 최고차항의 차수가 f(n)과 일치하거나 더 작은 함수의 집합이다.
   • 예를들어, O(n^2)은 n^2, 3n^2-49m 5n+19,n , 2nlogn+3n 등을 포함한다.
3. Ω - 표기법Ω - 표기법은 함수의 점근적 하한을 나타낸다.
   • Ω(f(n)) 은 점근적 증가율이 적어도 f(n)이 되는 모든 함수의 집합이다.
     다시말하면 Ω(f(n))은 최고차항의 차수가 f(n)과 일치하거나 더 큰 함수의 집합이다.
   • 예를들어, Ω(n^2)는 n^2, 3n^2-40, 4n^3+14, 2n^2logn+1 등을 포함한다.

+ Θ(g(n))은 O(g(n))과 Ω(g(n))의 교집합이다.