이제껏 코플릿 알고리즘 문제를 풀 땐 구현 여부만을 신경써서 풀었었다.
코드가 길어지고 지저분해 보일 때 더 나은 방법은 없을까 고민하곤 했지만 시간 복잡도를 고려한 것은 아니였다. 리츠코드나 프로그래머스 알고리즘 문제를 풀기 시작하면서 코드의 효율성과 정확성을 생각해보게 됐는데 이런 고민이 시작 복잡도와도 연결되어 있는 것 같다.

시간 복잡도

입력값의 증가/감소에 따라 시간이 얼마만틈 비례하여 증가/감소하는가

효율적인 알고리즘은 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 것이라 할 수 있다.

시간복잡도를 고려할 때 가장 먼저 보는것이 반복문이다.

Big-O 표기법

최악의 경우 입력값의 증가에 따라 시간 복잡도가 얼마나 증가하는지 표기하는 것으로 시간 복잡도를 표기하는 방법 중 하나이다.

O(1)

O(1)은 constant complexity라고 하며, 입력값이 증가해도 시간은 늘어나지 않는 것을 말한다.
입력값이 얼마나 커지는지 상관 없이 즉시 출력 값을 얻어낼 수 있다.

아래 알고리즘은 배열의 길이가 아무리 커져도 index에 접근해서 값을 얻을 수 있다.

function algorithm(arr, index) {
  return arr[index]
}

let arr = [1, 2, 3, 4, 5, 6]
let result = algorithm(arr, 3);
result; // 4

예시

• stack에서 push(), pop()

O(n)

O(n)은 linear complexity라고 하며, 입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것을 말한다.

algorithm 함수에선 n이 1씩 증가할 때마다 실행 시간이 1초씩 증가하며 같은 비율로 증가하고 있다.
another_algorithm 함수에서는 n이 1씩 증가할 때마다 실행시간은 2초씩 증가한다.
이때도 O(n)의 시간 복잡도를 가졌다 할 수 있다.
입력값이 커지면 커질수록 계수(n 앞에 있는 수)의 의미를 점점 퇴색하기 때문에, 같은 비율로 증가하고 있다면 2,5,10배로 증가하더라도 O(n)으로 표기한다.

function algorithm(n) {
	for (let i = 0; i < n; i++) {
	// do something for 1 second
	}
}

function another_algorithm(n) {
	for (let i = 0; i < 2n; i++) {
	// do something for 1 second
	}
}

예시

• for문

O(log n)

O(log n)은 logarithmic complexity라고 부르며 O(1) 다음으로 빠른 시간 복잡도를 가진다.

예시

• 이진트리 / BST(이진탐색트리)

O(n2)

O(n2)는 quadratic complexity라고 하며, 입력값이 증가함에 따라 시간이 그의 제곱수의 비율로 증가하는 것을 말한다.

입력값이 1인 경우 1초가 걸리던게 5일 때 25초가 걸린다면 시간 복잡도는 O(n2)이다.

function algorithm(n) {
  for(let i=0; i<n; i++) {
    for(let j=0; j<n; j++) {
      //do something for 1 second
    }
  }
}

n^3, n^5 도 모두 Big-O 표기법으로는 O(n2)라 표기한다.

예시

• 이중 for 문
• 삽입정렬(insertion sort), 거품정렬(bubble sort), 선택정렬(selection sort)

O(2n)

O(2n)은 exponential complexity라고 부르며 Big-O표기법 중 가장 느린 시간 복잡도를 가진다.

구현한 알고리즘의 시간 복잡도가 O(2n)이라면 다른 접근 방식을 고민해 보는 것이 좋다.

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

• 재귀로 구현하는 피보나치 수열
  한번 호출 할 때마다 본인을 2번 호출하게 되기 때문에

대략적인 데이터 크기에 따른 시간 복잡도

자료 참조 : 코드스테이츠