알고리즘 정의

알고리즘(영어: Algorithm)은
어떠한 문제를 해결하기 위해
정해진 일련의 절차나 방법을 공식화한 형태로 표현한 것,
계산을 실행하기 위한 단계적 절차를 의미합니다.

쉽게 말해, 알고리즘이란

• 어떤 입력값 조건으로부터
• 원하는 결과값을 얻기 위한
• 계산절차

라고 볼수 있습니다.

알고리즘 효율성 표현 방법 (big-O)

복잡도 개념

시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity)가 있어요.

• 시간 복잡도 : 알고리즘 실행 완료시까지 걸리는 시간과 알고리즘과의 관계
• 공간 복잡도 : 알고리즘 실행 완료를 위해 필요한 메모리(공간) 크기와 알고리즘과의 관계

big-O 표기법

복잡도를 표현할 때 big-O(빅-오) 표기법을 사용합니다.
big-O 표기법은 단순히 증가하는 비율을 나타내는 개념이므로
계수와 낮은 차수의 항을 무시해요.

big-O 방식으로 표현할 때, (예를 들면, 입력 크기를 무한대로 입력하여) 시간복잡도를 점근적으로 묘사한다고 말합니다.

예시로서, 만약 크기 n의 모든 입력에 대한 알고리즘에 필요한 시간이 최대 (어떤 n0보다 크지 않은 모든 n에 대하여) 5n^3 + 3n의 식을 가진다면, 이 알고리즘의 점근적 시간 복잡도는 O(n^3)이라고 할 수 있죠.

입력의 크기가 n일 경우, 점근 표기법 big-O를 사용하여 다음과 같이 나타냅니다.

1. O(1) : n에 관계없이 일정 시간 이하에 수행됨
2. O(log n)
3. O(n) : n에 비례하는 시간 이하에 수행됨
4. O(n log n)
5. O(n^2) : n^2에 비례하는 시간 이하에 수행됨
   O(n^3)
   ...
6. O(2^n)
7. O(n!)

Big-O Complexity Chart

* 출처: http://bigocheatsheet.com/

기울기가 높아질 수록 성능이 좋지 않은 것이므로, 가능하면 기울기가 낮은 알고리즘을 만들어야 겠죠.

• Exellent : O(1)
• Good : O(log n)
• Fair : O(n)
• Bad : O(n log n)
• Horrible :
  • O(n^2), O(n^3), ...
  • O(2^n)
  • O(n!)

빅오의 차이가 성능을 얼마나 좌우하는 지 알아볼까요? 숫자가 작을 수록 시간이 덜 걸리는 겁니다.

	O(n)	O(n log n)	O(n^2)	O(2^n)
n=1	1	0	1	2
n=10	10	23	100	1,024
n=100	100	460	10,000	0이 30개

n이 커질수록 성능의 차이가 현격히 벌어지는 것을 알 수 있습니다.

참고

정렬 알고리즘의 시간 복잡도

• 제로초 블로그: https://www.zerocho.com/category/Algorithm