효율적인 알고리즘에 대한 고민

요리사가 같은 시간 안에 더 많은 요리를 만들기 위해서는?

시간 복잡도(Time Complexity)는 문제를 해결하는 데 걸리는 시간과 입력의 함수 관계를 가리킴

여러가지 시간 복잡도 표기 방법

• $Big O$(빅-오) → 상한 점근(최악의 경우)
  최악의 경우 : 알고리즘의 실행 시간이 입력에 대해 가장 오래 걸리는 경우

• $BigΩ$(빅-오메가) → 하한 점근(최선의 경우)
  최선의 경우 : 알고리즘의 실행 시간이 입력에 대해 가장 짧게 걸리는 경우

• $BigΘ$(빅-세타) → 위 둘의 평균

아래 배열들에 대해 오름차순 정렬을 한다면? N의 범위 중에서 가장 큰 값이 입력되는, 최악의 경우(Test Case)까지 고려해야 하므로 주로 Big-O 표기법을 사용

대표적인 $BigO$ 표기법의 종류

출처 : Medium

$O(1)$

• 일정한 복잡도(constant complexity)

• 입력값이 증가하더라도 실행 시간이 늘어나지 않음

• 입력값의 크기와 관계없이, 즉시 출력값을 얻어낼 수 있음

• 예: 어떠한 배열의 특정 인덱스 위치의 요소 출력

$O(logN)$

• 로그 복잡도(logarithmic complexity)

• 시간 복잡도는 O(1) < O(logN) < O(N) 순으로 큼

• N이 커질수록 O(N)보다 O(1)에 더 가까워짐

• 매번 탐색 범위의 중간값을 제시할 때마다 경우의 수가 절반씩 줄어듦

• 예: 특성 숫자를 맞추는 Up & Down 게임

$O(N)$

• 선형 복잡도(linear complexity)

• 입력값이 증가함에 따라 실행 시간 또한 같은 비율로 증가

• 계수는 생략

  입력값(N)이 커짐에 따라 계수의 의미가 퇴색되기 때문
  아래 두 함수는 for 문의 반복 횟수가 다르지만, 모두 O(N)으로 표기(O(2N) → O(N))

$O(N^2)$

• 2차 복잡도(quadratic complexity)

• 입력값이 증가함에 따라 실행 시간이 N의 제곱수의 비율로 증가

• 2중 for 문법에서 보이는 시간 복잡도 → O(n²)

$O(2^n)$

• 지수 복잡도 or 기하급수적 복잡도(exponential complexity)

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

• 예시: 재귀로 구현한 피보나치 수열

int fibonacci(int N) {
	if (N <= 1) {
    	return 1;
    }
    return fibonacci(N - 1) + fibonacci(N - 2);
}

$O(N!)$

• 팩토리얼 시간 복잡도(factorial complexity)

• 시간 복잡도가 가장 큼

• 예시: 3개의 서로 다른 공에 대한 총 6(3!)가지의 순열(permutation)