[알고리즘] 기초 개념

1) 알고리즘이란?

• 알고리즘이란 어떠한 문제를 해결하기 위한 여러 동작들의 모임을 기술한 것
• 명확한 입력과 출력을 가지고 있어야 함

알고리즘의 요건

• 입출력 : 입력과 출력을 가지고 있어야 함
• 정확성 : 주어진 입력에 대해 항상 올바른 답을 주어야 함
• 유한성 : 유한 시간 내에 종료되어야 함
• 효율성 : 시간적, 공간적 효율성을 가져야 함
• 수행성(컴퓨터) : 컴퓨터로 수행이 가능해야 함

알고리즘의 분석 기준

• 정확성
  • 모든 유효한 입력에 대해서 유한 시간 내에 올바른 해를 찾아내는가를 판단
• 공간 복잡도
  • 해를 찾아내는 데 사용되는 기억 장소의 사용량
  • 입력 개수에 따른 증가율이 중요함
• 시간 복잡도
  • 해를 찾아내는 데 걸리는 시간 절대 시간보다는 입력 개수에 따른 증가율이 중요함

2) 알고리즘의 분석

• 정확성 확인(무결성 확인)
  • 모든 유효한 입력에 대해서 유한 시간 내에 올바른 해를 찾아내는가를 판단하기 위함
• 효율성 확인
  • 한정된 자원(기억 장소 사용량, 수행 시간)에서 효율적으로 작동하는지 확인하기 위함
• 궁극적으로 알고리즘을 분석하여 얻는 이점
  • 알고리즘을 분석 → 체계적이고 효율적으로 생각하는 훈련을 할 수 있음
  • 문제를 해결하기 위해 중요한 것과 중요하지 않은 것을 판단할 수 있음
  • 문제를 단순화하여 생각할 수 있음
  • 다른 사람의 아이디어에 대한 효율성을 판단할 수 있음

알고리즘의 수행 시간

• 알고리즘의 효율성을 분석하는 방법은 다양하지만, 많은 경우에 알고리즘의 수행 시간을 이용하여 효율성을 분석
• 시간복잡도
  • 입력 크기에 비례하여 작업시간이 어떠한 비율로 증가하는지 확인함
  • 실측으로 시간을 측정하는 경우 프로그래밍 언어, 컴퓨터의 성능, 프로그래머의 실력 등의 다양한 변수에 따라 달라질 수 있음
  • 최선 경우 분석(Best Case Analysis)
  • 최악 경우 분석(Worst Case Analysis)
  • 평균 경우 분석(Average Case Analysis)

알고리즘의 공간 사용량

• 공간복잡도
  • 입력 크기에 비례하여 작업 공간이 어떠한 비율로 증가하는지 분석하는 것
  • 실측으로 공간사용량을 측정하는 경우 프로그래밍 언어, 프로그래머의 실력 등의 다양한 변수에 따라 달라질 수 있음

3) 점근적 표기법

• 입력의 크기가 충분히 큰 문제
• 알고리즘의 효율성이 중요함
• 비효율적인 알고리즘은 치명적임
• 입력의 크기가 충분히 큰 경우에 대한 분석을 점근적 분석이라고 함
• O(Big-Oh) 표기법
  • 최악의 경우: 어떠한 경우에도 표기된 함수만큼의 성능은 보장 (점근적 상한)
• Ω(Big-Omega) 표기법
  • 최선의 경우: 운이 좋다면, 알고리즘은 표기된 함수만큼의 성능을 낼 수도 있음 (점근적 하한)
• Θ(Theta) 표기법
  • 알고리즘의 거의 정확한 성능

O(Big-Oh) 표기법

• O(𝑔(𝑛)) = {݂(𝑛)

  충분히 큰 모든 𝑛에 대해 ݂(𝑛) ≤ 𝑐𝑔(𝑛)}인 양의 상수 𝑐가 존재함}

• 점근적 상한선(Asymptotic Upper Bound)
• 최악의 경우의 알고리즘 수행 시간을 나타냄
  • 최악의 경우에도 성능을 보장하기 때문에 가장 많이 사용하는 알고리즘 성능 표기법
• 복잡도 f(𝑛)과 𝐎-표기를 그래프로 나타낸 것
  • 𝑛이 증가함에 따라 𝐎(𝑔(𝑛))이 점근적 상한이 됨
  • 𝑔(𝑛)이 𝑛𝟎보다 큰 모든 𝑛에 대해서 항상 ݂(𝑛)보다 크다는 것을 보여줌

Ω(Big-Omega) 표기법

• Ω(𝑔(𝑛)) = {݂(𝑛)

  충분히 큰 모든 𝑛에 대해 𝑐𝑔(𝑛) ≤ ݂(𝑛)}인 양의 상수 𝑐가 존재한다.}

• 점근적 하한선(Asymptotic Lower Bound)
• 최선의 경우의 알고리즘 수행 시간을 나타냄
  • 거의 쓰이지 않음
• 복잡도 f(𝑛)과 𝛀-표기의 그래프
  • 𝑛이 증가함에 따라 𝛀(𝑔(𝑛))이 점근적 하한이라는 것
  • 즉, 𝑔(𝑛)이 𝑛𝟎보다 큰 모든 𝑛에 대해서 항상 ݂(𝑛)보다 작다는 것을 보여줌

Θ(Theta) 표기법

• Θ(𝑔(𝑛)) = {𝑓(𝑛)

  충분히 큰 모든 𝑛에 대해 𝑐1𝑔(𝑛) ≤ 𝑓(𝑛) ≤ 𝑐2𝑔(𝑛)}인 양의 상수 𝑐1, 𝑐2가 존재함

• 점근적 상한선과 점근적 하한선의 교집합(Asymptotic Tight Boun
• 복잡도 ݂(𝑛)과 𝚯-표기를 그래프로 나타낸 것
• 𝑛𝟎보다 큰 모든 𝑛에 대해서 𝚯-표기가 상한과 하한을 동시에 만족한다는 것을 보여줌