[알고리즘] 복잡도와 표기법

알고리즘의 종류

• Path Finder
  최단 경로를 찾는 알고리즘
• Compression Algorithm
  이미지의 퀄리티 손상 없이 처리하는 압축 알고리즘
• Encryption Algorithm
  암호화 알고리즘

이외에도 많은 종류가 있다.

복잡도란?

• 알고리즘의 성능을 나타내는 척도이다.
• 대략적인 효율성을 분석하는 데 사용하는 방법

복잡도의 종류

• 시간 복잡도 (Time Complexity)
• 공간 복잡도 (Space Complexity)

공간 복잡도

공간 복잡도란 프로그램 실행과 완료에 얼마나 많은 공간이 필요한지를 나타낸다.
프로그램의 성능을 분석하는 방법 중 하나로 프로그램이 얼마나 많은 공간(메모리)를 차지하느냐를 분석하는 방법이다. 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미한다. 최근 컴퓨터의 성능 발달로 인해 공간 복잡도의 중요성이 월등히 낮아졌다고 한다.

시간 복잡도 및 판단 기준

시간 복잡도란 특정 크기에 입력을 기준으로 할 때 필요한 연산의 횟수를 나타낸다.
특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지를 의미한다.

• 최선의 경우 (Best Case)
• 평균적인 경우 (Average Case)
• 최악의 경우 (Worst Case)

• 빅 오메가 표기법 ( Big-Ω )
  최선의 경우를 판단하는 표기법이다.
• 빅 세타 표기법 ( Big-θ )
  평균적인 경우를 판단하는 표기법으로 빅 오와 빅 오메가의 중간이라고 생각하면 된다.
• 빅 오 표기법 ( Big-O )
  최악의 경우를 판단하는 표기법이다.

표기법의 접근 방식

빅 오메가 표기법	= 하한 접근
빅 세타 표기법		= 상한 / 하한 접근
빅 오 표기법		= 상한 접근

주로 빅 오 표기법을 사용하는데 그 이유는 최악의 경우를 고려 함에 따라 실행되는 과정에서 최악의 경우가 발생하지 않도록 대비하는 것이기에 Big-O 표기법을 많이 사용한다. 또 알고리즘이 복잡해질수록 평균을 구하기 어려워진다. 이 때문에 최악의 경우로 알고리즘 성능을 파악한다.