Algorithm

알고리즘
어떠한 문제를 해결하기 위해,
정해진 일련의 절차나 방법을 공식화한 형태로 표현한 것,
계산을 실행하기 위한 단계적 절차
@Wikipedia - 알고리즘

❗ 알고리즘은,

1. 어떤 목적을 달성하거나, 결과물을 만들기 위해, 거쳐야하는 일련의 과정들을 의미한다.
2. 그 과정은 다양하며, 여러가지 상황에 따라, 알고리즘은 모두 다르다.

📌 시간복잡도가 가장 낮은 알고리즘을 선택하여 사용한다.

시간복잡도
문제를 해결하는데 걸리는 시간과 입력의 함수 관계
@Wikipedia - 시간복잡도

❗ 시간복잡도는,

간단하게 정의하면, 알고리즘의 성능을 설명하는 것이다.
알고리즘이 문제를 해결하기 위한, 시간 및 연산의 횟수를 말한다.

---

알고리즘을 평가하는 기준에는 수행시간과 메모리 사용량이 있다.

수행시간에 해당하는 것이 시간복잡도이고,
메모리 사용량에 해당하는 것이 공간복잡도이다.

cf.
저장 기술의 발달로,
현재는 시간복잡도를 우선 고려하는 경우가 많다.

---

연산 횟수의 기준은 3가지가 있다.
1. 최선의 경우 ➡ 오메가 표기법
2. 최악의 경우 ➡ 세타 표기법
3. 평균적인 경우 ➡ 빅오 표기법

📌 최악의 경우로 알고리즘의 성능을 파악한다.
why?
최선과 최악이 아닌, 평균적인 경우가 가장 이상적일 것이라 생각되지만,
알고리즘이 복잡해질수록, 평균적인 경우를 구하기 어려워지기 때문이다.

---

❗ Big - O 표기법은,

불필요한 연산을 제거하여, 알고리즘 분석을 쉽게 할 목적으로 사용된다.

• 상수항 무시
  $O(3N)$ ➡ $O(N)$
  $O(N^2 + 2)$ ➡ $O(N^2)$

• 영향력 없는 항 무시
  $O(N^2 + N)$ ➡ $O(N^2)$

📌 자주 사용되는 Big - O 실행 시간
$O(1)$ < $O(log n)$ < $O(n)$ < $O(n log n)$ < $O(n^2)$ < $O(2^n)$ < $O(n!)$ < $O(n^n)$

cf.
항상 $N$ 변수 하나만 사용되는 것은 아니다.
문제 상황에 따라 하나만 사용될 수도 있고,
여러 개의 변수가 사용될 수도 있으니 주의해야한다.

---

• $O(1)$ : 상수
  입력에 관계없이 복잡도는 동일하게 유지된다.

• $O(N)$ : 선형
  입력이 증가하면 처리 시간 또는 메모리 사용이 선형적으로 증가한다.

• $O(N^2)$ : Sqare
  반복문이 두 번 있는 경우

• $O(log n) O(n log n)$
  주로 입력 크기에 따라 처리 시간이 증가하는 정렬 알고리즘에서 많이 사용된다.

cf.

• 하나의 루프를 사용하여 단일 요소 집합을 반복하는 경우 : $O(n)$
• 절반 이상을 반복하는 경우 : $O(n / 2)$ ➡ $O(n)$
• 두 개의 다른 루프를 사용하여 각각 반복하는 경우 : $O(n * m)$ ➡ $O(n^2)$

Reference
알고리즘의 시간 복잡도와 Big-O 쉽게 이해하기
알고리즘 공부 시작 방법 및 순서
빅오 표기법, 시간 복잡도, 공간 복잡도
알고리즘과 시간복잡도