[자료구조] 시간복잡도와 공간복잡도

시간복잡도

개념

• 시간 복잡도는 알고리즘이 실행되는 시간이 입력 크기에 따라 어떻게 변하는지를 나타낸다.
• 일반적으로 입력의 크기(n) 에 대한 함수로 표현되며, 가장 널리 사용되는 표기법은 빅오 표기법(Big-O Notation)이다.
• 시간 복잡도는 최악의 경우를 기준으로 측정하며, 알고리즘의 성능을 비교할 때 중요한 지표이다.

우리는 변수와 배열을 사용해서 각각에 맞는 알고리즘으로 해결할 수 있다는 걸 알고있다.

 

평균을 구하는 문제 예시)

• 변수는 변수에 맞는, 배열은 배열에 맞는 알고리즘을 이용.
• 같은 자료구조를 쓰더라도 알고리즘을 여러가지가 될 수 있음.
  • 1. 배열의 모든 숫자를 더하고 원소의 개수만큼 나눠라.
  • 2. 배열의 첫 번째 원소와 두 번째 원소, 세 번째 원소를 더하고 3을 나눠라.

 

더 좋은 알고리즘은 사용자에 요구에 따라 다를 것이다.

• 1. 메모리를 더 적게 사용하는 싶은 사용자
  • 메모리를 적게 사용하는 알고리즘이 더 좋은 알고리즘
• 2. 속도를 더 빠르게 사용하고 싶은 사용자
  • 메모리를 더 많이 사용하더라도 속도가 더 빠른 알고리즘이 더 성능이 좋은 알고리즘

 

사용자가 중요시하는 요구가 다르지만 일반적으로는 알고리즘의 속도를 성능의 척도로 사용한다.

이를 시간 복잡도라고 부른다 - ("특정 알고리즘이 어떤 문제를 해결하는 데 걸리는 시간").

 

하지만 시간을 측정해서 알고리즘을 평가하기엔 현실적으로 어려운 문제가 있다. 사용자마다 컴퓨터 성능이 다르기 때문이다.

따라서 알고리즘을 평가할 때는 시간을 측정하는게 아닌 코드에서 성능에 많은 영향을 주는 부분을 찾아 실행시간을 예측하는 것이다. 

 

그렇다면 코드에서 성능에 많은 영향을 주는 부분은 어떤 것일까?

• 반복문이다. 반복문이 여러번 반복될수록 실행시간이 길어진다.
• 따라서 특정 알고리즘의 성능을 평가할 때는 해당 알고리즘의 반복문을 보고 평가한다.
• 예시: "주어진 배열에서 5를 찾으시오."

 

그렇다면 사용한 알고리즘의 성능을 어떤 식으로든 표현할 수 있어야 한다.

하지만 우리가 찾는 데이터가 배열에 어디있는지에 따라서 성능은 천차만별이다.

• 최선의 경우: 한 번에 찾음 - (Big- Ω)
• 최악의 경우: 배열의 길이만큼 걸림 - (Big - O)
• 평균의 경우: 배열의 길이 중간 만큼 걸림 - (Big - θ)

 

최악의 경우를 평가하는 것을 빅 O를 사용한다고 한다.

• 일차함수의 모양으로 데이터 수를 나타내는 n
• 위에 예시에서 최악의 경우는 찾는 데이터가 배열의 길이 끝에 있을 때이다.
• 이를 빅 O 표기법으로 O(n)으로 표기한다.

---

빅 O 표기법

입력이 늘어날 때 계산량이 늘어나는 척도를 나타내기 위한 것

 

빅오 표기법은 별도의 이야기가 없으면 보통 최악의 상황을 가정해서 표기한다.

 

O(1): 상수시간 알고리즘

• 입력의 크기에 상관없이 상수의 시간이 걸린다는 의미
• 계산량이 꼭 1번일 필요는 없다.
• 문제를 해결하는데 입력의 크기에 상관없이 100번의 계산이 걸린다고 하더라도 상수이기 때문에 O(1)로 표기

O(n): 선형시간 알고리즘

• 데이터가 수가 1개라면 1, 데이터가 많아지면 그에 비례해서 계산량이 많아진다.

 

O(n²): 이차 시간 복잡도

• 중첩된 반복문이 있을 때, 입력 크기가 증가할수록 시간이 제곱 형태로 증가하는 경우.
• 예: 버블 정렬.

O(log n): 로그 시간 복잡도

• 입력 크기가 증가할수록 실행 시간이 천천히 증가하는 경우.
• 예: 이진 탐색(Binary Search).

O(n log n):

• 예: 병합 정렬(Merge Sort), 퀵 정렬(Quick Sort)의 평균 시간 복잡도.

 

여기서 중요한 것은 알고리즘의 정확한 실행 시간을 계산하는 것이 아니라, 데이터 양의 증가에 따른 성능의 변화 추세를 이해하는 것이다.

 

계산 예시 1)

for (int i = 0; i < n; i++) {
    System.out.println(i);
}

• 이 코드는 n번 반복하므로 시간 복잡도는 O(n)이다.

 

계산 예시 2)

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        System.out.println(i + ", " + j);
    }
}

• 여기서는 이중 반복문이고, 내부 for 루프가 외부 루프당 n번 실행되므로, 전체 반복 횟수는 n * n이다.
• 따라서 시간 복잡도는 O(n²)이다.

 

특징

• 계산에 가장 많은 영향을 미치는 항만 표기
• 빅오 표기법으로 표기할 때는 상수는 큰 의미가 없으므로 제거
• n² + 2n + 100 의 성능을 보이는 알고리즘이 있다면  - O(n²)
• 3n² + 100n 의 성능을 보이는 알고리즘이 있다면 - O(n²)

빅오 표기법은 정확한 성능을 측정하는 것이 목표가 아니라 매우 큰 데이터가 들어왔을 때의 대략적인 추세를 비교하는 것이 목적이다. 따라서 데이터가 매우 많이 들어오면 추세를 보는데 상수는 크게 의미가 없어진다.

 

참고

• 빅오 표기법은 성능을 정확하게는 표현하지 못한다.
• 단순히 해당 알고리즘의 입력이 늘어날 때 계산량이 얼마나 늘어나는지 표현하는 것이기 때문이다.
• 그 외에도 성능은 O(log n), O(n log n), O(n²), O(2ⁿ), O(n!) 등이 있다.

---

공간 복잡도

개념

• 공간 복잡도는 알고리즘이 사용하는 메모리의 양을 나타낸다.
• 이는 입력 크기(n)에 따라 알고리즘이 추가적으로 사용하는 메모리의 양이 어떻게 변하는지를 측정하는 것이다.
• 일반적으로 프로그램이 사용하는 변수, 배열, 객체, 재귀 호출 스택 등이 공간 복잡도에 영향을 미친다.
• 공간 복잡도 역시 입력 크기(n)에 대한 함수로 표현되며, 시간 복잡도와 마찬가지로 빅오 표기법으로 나타낸다.

 

계산 방법

• 공간 복잡도를 계산할 때는 주로 알고리즘이 사용하는 추가적인 공간(변수, 자료구조)을 분석한다.
• 즉, 입력 데이터의 크기 외에 추가로 할당되는 메모리 양을 고려한다.

 

일반적인 공간 복잡도 사례

• O(1): 상수 공간 복잡도. 입력 크기와 무관하게 고정된 양의 메모리만 사용하는 경우.
• O(n): 선형 공간 복잡도. 입력 크기에 비례하여 메모리 사용량이 증가하는 경우.
• O(n²): 이차 공간 복잡도. 예: 2차원 배열을 사용하는 경우.

 

계산 예시 1)

int sum = 0;
for (int i = 0; i < n; i++) {
    sum += i;
}

• 여기서 sum이라는 상수 크기의 변수만 사용하고 있으며, 추가로 사용하는 메모리가 없기 때문에 공간 복잡도는 O(1)이다.

 

계산 예시 2)

int[] arr = new int[n];
for (int i = 0; i < n; i++) {
    arr[i] = i;
}

• 이 경우 n개의 정수를 저장하는 배열 arr이 추가로 사용되므로, 공간 복잡도는 O(n)이다.

---

참고

최선/평균/최악 시간 복잡도

• 최선 시간 복잡도: 알고리즘이 가장 빠르게 실행될 때의 복잡도를 나타낸다. 하지만 대부분의 경우에는 평균이나 최악의 경우를 더 중요하게 다룬다.
• 평균 시간 복잡도: 일반적인 경우에서 알고리즘의 실행 시간을 나타낸다.
• 최악 시간 복잡도: 입력이 최악의 경우(가장 시간이 오래 걸리는 경우)일 때의 실행 시간을 나타낸다. 알고리즘 분석에서는 주로 최악 시간 복잡도를 기준으로 평가한다.

공간-시간 상관관계

• 공간과 시간 간의 상관관계: 효율적인 알고리즘 설계는 공간과 시간의 균형을 맞추는 것이 중요하다. 예를 들어, 메모리를 더 많이 사용하면 실행 시간을 줄일 수 있고, 반대로 메모리 사용을 줄이면 실행 시간이 늘어날 수 있다. 이 둘 사이의 절충점을 찾는 것이 핵심이다.

---