알고리즘에 대하여(시간 복잡도 공간 복잡도 ...)

알고리즘이란

알고리즘은 어떤 문제를 해결하기 위해서 일련의 절차를 정의하고, 공식화한 형태로 표현한 일종의 문제의 풀이 방법, 해(解)를 의미합니다. 프로그래밍에서는 input 값을 통해 output 값을 얻기 위한 계산 과정을 의미합니다.

• Input(입력)
  알고리즘은 출력에 필요한 자료를 입력받을 수 있어야 합니다.
  하지만 꼭 입력을 받지 않아도 되는 알고리즘도 있습니다.
  (ex. 원주율(pi)의 1조 번째 자리 수를 구하려는 경우 입력은 없지만 출력은 있다.)

• Output(출력)
  알고리즘은 실행이 되면 적어도 한 가지 이상의 결과를 반드시 출력해야 합니다.
  만약 알고리즘에 출력이 없다면 이 알고리즘은 끝이 났는지,
  끝이 나지 않았는지 확인할 길이 없기 때문입니다.

• Finiteness(유한성)
  알고리즘은 유한한 명령어를 수행한 후, 유한한 시간 내에 종료해야 합니다.
  이는 알고리즘은 실행된 후에는 반드시 종료되어야 한다는 말과도 같습니다.
  알고리즘이 무한히 실행이 된다면 무한히 기다려야 할 것이며,
  그것은 출력의 기약이 없는 알고리즘일 것입니다.

• Definiteness(명확성)
  알고리즘의 각 단계는 단순하고 명확해야 하며, 모호해서는 안 됩니다.

• Efficiency(효율성)
  알고리즘은 가능한 한 효율적이어야 합니다.
  모든 과정은 명백하게 실행 가능해야 하며,
  실행 가능성이 떨어지는 알고리즘은 효율적이지 못한 알고리즘이라 볼 수 있습니다.
  알고리즘은 시간 복잡도와 공간 복잡도를 통해 결정이 되므로,
  시간 복잡도와 공간 복잡도가 낮을 수록 효율적인 알고리즘이라 볼 수 있습니다.

---

시간 복잡도

입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?

시간 복잡도를 표기하는 방법

1. Big-O(빅-오)
2. Big-Ω(빅-오메가)
3. Big-θ(빅-세타)

위 세 가지 표기법은 시간 복잡도를 각각 최악, 최선, 중간(평균)의 경우에 대하여 나타내는 방법입니다. 이 중에서 Big-O 표기법이 가장 자주 사용됩니다. 빅오 표기법은 최악의 경우를 고려하므로, 프로그램이 실행되는 과정에서 소요되는 최악의 시간까지 고려할 수 있기 때문입니다. 최악의 경우가 발생하지 않기를 바라며 시간을 계산하는 것보다는 최악의 경우도 고려하여 대비하는 것이 바람직합니다. 따라서 다른 표기법보다 Big-O 표기법을 많이 사용합니다.

Big-O 표기법의 종류

• O(1)
  O(1)는 constant complexity라고 하며, 입력값이 증가하더라도 시간이 늘어나지 않습니다.

function O_1_algorithm(arr, index) {
	return arr[index];
}

let arr = [1, 2, 3, 4, 5];
let index = 1;
let result = O_1_algorithm(arr, index);
console.log(result); // 2

• O(n)
  O(n)은 linear complexity라고 부르며,
  입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것을 의미합니다.
  예를 들어 입력값이 1일 때 1초의 시간이 걸리고,
  입력값을 100배로 증가시켰을 때 1초의 100배인 100초가 걸리는 알고리즘을 구현했다면,
  그 알고리즘은 O(n)의 시간 복잡도를 가진다고 할 수 있습니다.

function O_n_algorithm(n) {
	for (let i = 0; i < n; i++) {
	// 입력값(n)이 1 증가할 때마다 코드의 실행 시간이 1초씩 증가합니다.
	}
}

function another_O_n_algorithm(n) {
	for (let i = 0; i < 2n; i++) {
	// 입력값이 1 증가할때마다 코드의 실행 시간이 2초씩 증가합니다.
	}
}

• O(log n)
  O(log n)은 logarithmic complexity라고 부르며 Big-O표기법중 O(1) 다음으로 빠른 시간 복잡도를 가집니다. BST의 값 탐색도 같은 로직으로 O(log n)의 시간 복잡도를 가진 알고리즘(탐색기법)입니다.

• O(n^)
  O(n2)은 quadratic complexity라고 부르며, 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는 것을 의미합니다.

function O_quadratic_algorithm(n) {
	for (let i = 0; i < n; i++) {
		for (let j = 0; j < n; j++) {
		
		}
	}
}

function another_O_quadratic_algorithm(n) {
	for (let i = 0; i < n; i++) {
		for (let j = 0; j < n; j++) {
			for (let k = 0; k < n; k++) {
			
			}
		}
	}
}

• O(2^)
  O(2n)은 exponential complexity라고 부르며 Big-O 표기법 중 가장 느린 시간 복잡도를 가집니다. 재귀로 구현하는 피보나치 수열은 O(2n)의 시간 복잡도를 가진 대표적인 알고리즘입니다.

function fibonacci(n) {
	if (n <= 1) {
		return 1;
	}
	return fibonacci(n - 1) + fibonacci(n - 2);
}

---

공간 복잡도

공간 복잡도는 알고리즘이 수행되는 데에 필요한 메모리의 총량을 의미합니다.
즉 프로그램이 필요로 하는 메모리 공간을 산출하는 것을 의미합니다.
프로그램이 요구하는 공간은 고정적인 공간과 함께 가변적인 공간을 함께 요구합니다.
여기서 집중해야 할 부분은 가변적인 공간입니다.
왜냐하면 고정적인 공간은 처리할 데이터의 양에 무관하게 항상 요구되는 공간으로서,
프로그램의 성능에 큰 영향을 주지 않기 때문입니다.
공간 복잡도 계산은 시간 복잡도 계산과 비슷하게 빅 오 (Big-O) 표기법으로 표현합니다.
보통 시간 복잡도에 맞다면 공간 복잡도도 얼추 통과하기 때문에
알고리즘 구현 시 공간 복잡도에 실패했다면,
보통은 변수를 설정할 때 쓸데없는 공간을 많이 차지하도록 설정했을 경우가 많을 것이니 그것부터 확인해야 합니다.