시간복잡도와 공간복잡도

[jslee7420]

시간복잡도와 공간 복잡도

좋은 알고리즘, 효율적인 알고리즘이란 적은 시간안에 적은 자원을 소비해서 답을 도출하는 알고리즘을 말합니다. 알고리즘의 속도와 자원 사용량을 나타내는 지표를 각각 시간 복잡도와 공간 복잡도라고 합니다.

시간복잡도(Time Complexity)

시간 복잡도는 서로 다른 알고리즘의 효율성을 비교할 때 사용합니다. 시간 복잡도(Time Complexity)는 알고리즘의 절대적인 실행 시간을 나타내는 것이 아닌 알고리즘을 수행하는 데 연산들이 몇 번 이루어지는 지를 숫자로 표기합니다. 그런데 연산(Operation)의 실행 횟수는 보편적으로 그 값이 변하지 않는 상수(Constant)가 아니라 입력한 데이터의 개수를 나타내는 n에 따라 변하게 됩니다.연산의 개수를 입력한 데이터의 개수 n의 함수로 나타낸 것을 시간 복잡도 함수라고 말합니다. 시간 복잡도에는 몇 가지 규칙이 있습니다.

1. 입력값(n)은 항상 0보다 크다.
   입력값이 음수일 수는 없습니다. 그래서 복잡도는 항상 0보다 크다고 가정하고 계산을 해야합니다.
2. 함수는 많은 입력값이 있을 때 더 많은 작업을 하게 됩니다.
   더 많은 입력값이 주어지면 어떤 작업을 하는 데 필요한 계산이나 처리 시간이 길어집니다.
3. 시간 복잡도에서는 모든 상수를 삭제합니다. 만약 어떤 알고리즘의 복잡도가 3n 이라면 3은 고려하지 않고 복잡도는 n이 됩니다. 2n, 3n, 10n 모두 복잡도가 n 인 알고리즘입니다.
4. 낮은 차수의 항들은 무시합니다.
   시간 복잡도에서는 입력값이 작은 값은 고려하지 않고 큰 값에 대해서만 생각을 하므로 n 이 무한으로 커진 경우를 가정하고 비교해야 합니다. 이런 이유로 시간 복잡도에서는 낮은 차수의 항들은 무시합니다.
5. 시간 복잡도 함수가 log 함수를 포함할 경우 밑은 무시합니다.
   모든 로그는 서로 배수 관계입니다. 그래서 복잡도에 관해서 이야기할 때는 로그의 밑에 대해서는 고려하지 않아도 됩니다. 로그의 밑은 무시하고 로그 ( logn ) 알고리즘이라고만 말하면 됩니다.
6. 등호를 사용하여 표현합니다.
   2n 은 O(n) 과 같습니다. 여기서 O(n) 은 2n 이 어떤 함수의 집합에 속한다는 의미를 가집니다. 그렇기 때문에 아래와 같은 등호를 활용하여 이 관계를 수학적으로 쓸 수 있습니다. 2n = O(n), 2n ∈ O(n)

접근적 표기법(Big Oh Notation)

시간복잡도는 입력 크기에 대한 함수로 표기하는데 이를 단순한 함수로 표현하기 위해 점근적 표기를 사용합니다. 이는 입력이 무한으로 커질때의 복잡도를 간단하게 표현하기 위한 방법입니다.

위 그래프는 복잡도가 n 인 알고리즘에 점근적 표기법을 적용한 결과입니다. x축은 복잡도 n, y축은 필요한 일의 양이나 메모리를 의미합니다.

다른 알고리즘이 이 그래프의 어떤 위치에 있는지에 따라 복잡도 n 인 알고리즘과 다른 알고리즘의 복잡도를 비교할 수 있습니다. 다른 알고리즘이 복잡도 n 인 알고리즘의 아래에 있다면, 같은 일을 하는 데 시간이 덜 들기 때문에 더 빠른 알고리즘이라 합니다. 반대로, 복잡도 n 인 알고리즘의 위에 있다면, 더 느린 알고리즘입니다.

점근적 표기법에서는 이러한 알고리즘 간의 관계를 다음과 같이 표현합니다.

• O (빅 오 복잡도) : 비교 대상인 그래프가 일치 혹은 아래에 있을 때. 비교 대상인 다른 알고리즘과 같거나 더 빠르다
• θ (세타 복잡도) : 비교 대상인 그래프가 일치할 때. 비교 대상인 다른 알고리즘과 같다.
• Ω (빅 오메가 복잡도) : 비교 대상인 그래프가 일치 혹은 위에 있을 때. 비교 대상인 다른 알고리즘과 같거나 느리다.
• o (리틀 오 복잡도) : 비교 대상인 그래프가 아래에 있을 때. 비교 대상인 다른 알고리즘보다 더 빠르다.
• ω (리틀 오메가 복잡도) : 비교 대상인 그래프가 위에 있을 때. 비교 대상인 다른 알고리즘과 느리다.

Big-O 표기 연산시간 크기 관계

Olog(1) < Olog(logn) < Olog(n) < O(nlogn) < O(n^2) < O(n^3) < O(e^n)

공간복잡도(Space Complexity)

공간 복잡도(Space Complexity)란 알고리즘을 수행시키기 위해 필요한 기억장치(memory)의 크기를 의미합니다.

공간복잡도는 총 공간 요구 = 고정 공간 요구 + 가변 공간 요구로 나타낼 수 있으며 수식으로는 S(P) = c + Sp(n) 으로 표기합니다.

• 고정 공간: 입력과 출력의 횟수나 크기와 관계없는 공간의 요구(코드 저장 공간, 단순 변수, 고정 크기의 구조 변수, 상수)
• 가변 공간: 해결하려는 문제의 특정 인스턴스에 의존하는 크기를 가진 구조화 변수들을 위해서 필요로 하는 공간, 함수가 순환 호출을 할 경우 요구되는 추가 공간이다. 즉 동적으로 필요한 공간 동적으로 필요한 공간.

일반적으로 알고리즘의 공간복잡도를 분석할 때는 위의 두 가지 중 두 번째 것을 계산합니다. 공간 복잡도도 시간 복잡도와 유사하게 빅오 표기법을 사용합니다.

int sum(int a[], int n)
{
  int x = 0;
  for(int i = 0; i < n; i++) {
    x  = x + a[i];
  }
  return(x);
}

위 알고리즘에서는 총 4 개의 변수를 사용합니다.

• int arr[n] : 4*n byte (입력 공간)
• int n : 4 byte (입력 공간)
• int x : 4 byte (보조 공간)
• int i : 4 byte (보조 공간)

총 4n + 12의 메모리를 요구하고 이를 빅오 표기법으로 표현하면 O(n)이 됩니다.

[jslee7420]

빅오 표기법에 대해서 설명해주세요