[DataStructure] 시간복잡도와 공간복잡도

시간복잡도와 공간복잡도

---

효율적인 알고리즘을 작성하기 위해서 시간복잡도 와 공간복잡도 이 두가지 요소를 놓고 평가하는데, 

특별히 시간 복잡도를 중요시해요. 그 이유는 요즘의 컴퓨터는 메모리가 과거에 비해 용량이 커져서, 시간 복잡도를 더 중요하게 본다고 해요.그렇다고 쓸데없는 메모리 선언을 통해 굳이 긁어서 부스럼을 만들 필요는 없겠죠, 동시에 메모리의 가격이 낮아지고, 모던 프로그래밍 언어에서는 메모리를 관리해주는 많은 옵티마이제이션이 들어가서 상대적으로 덜 중시될 수 있죠. 동시에, 시간 복잡도와 공간 복잡도는 반비례하는 경향이 있다고 합니다.

 

알고리즘 효율에서 가장 중요한 부분은 "n이 커질 때 알고리즘의 단계가 얼마만큼 증가하는가" 이고, 이것을 잘 타나내는 빅O표기법을 사용해요.

 

소규모 데이터를 다루는 경우 우수한 성능의 알고리즘과 그렇지 않은 알고리즘 사이에 차이가 거의 없습니다. 퀵 정렬이 훨씬 우수한 성능을 갖고 있지만, 오히려 소규모 데이터를 정렬할 때에는 삽입 정렬을 사용하는 편이 더 나은 효율을 보이죠. 알고리즘 성능 차이는 대규모 데이터를 다룰 때 두드러집니다. 그 규모가 무한대에 가까워지단면 그 차이는 아주 분명해지겠죠.

 

그렇다면, 시간 및 공간 복잡도의 경우 평가 방법이 3가지가 있는데요,

• 최상 : 오메가 표기법 (Big-Ω Notation)
• 평균 : 세타 표기법 (Big-𝛳 Notation)
• 최악 : 빅오 표기법 (Big-O Notation)

 

빅 O 표기법은 최악의 경우 알고리즘 수행 시간을 나타내요. 다시 말해, 알고리즘을 사용하는 어떤 경우에도 보장되는 알고리즘의 성능이라고 할 수 있습니다. 최악의 경우에 대한 알고리즘 수행 시간이 가장 쓸모가 많다 보니 가장 많이 사용하는 알고리즘 성능 표기법으로 빅O표기법이라고 하네요.

 

 

 

 

시간 복잡도 Time Complexity

---

 

  O(1) : 상수 시간(constant)        🟩🟩    

입력되는 자료의 크기에 관계없이 복잡도는 동일하게 유지

void add(int a, int b) {
    return a + b;
}

• 알고리즘 : 해시 테이블

 

 

  O(log N) : 로그 시간 (Logarithmic)         🟧🟧

로그 시간 복잡도는 상수 시간에 이어 두 번째로 효율적인 시간 복잡도에요. 데이터의 로그에 비레해 알고리즘의 단계가 늘어날 때, 알고리즘이 로그 시간으로 실행된다고 말해요. 로그 시간 복잡도는 실행을 반복할 때마다 알고리즘의 탐색 범위를 1/2 로 줄여 나가는 이진 탐색과 같은 알고리즘에서 볼 수 있어요.

데이터 세트가 커짐에 따라 알고리즘의 실행에 필요한 단계가 천천히 늘어나는 알고리즘을 말해요.

• 알고리즘 : 이진 탐색

 

 

 

  O(N) : 선형 시간 (Linear)        🟪🟪

입력 자료의 수에 따라 선형적으로 실행 시간이 걸리는 경우죠. 입력이 증가하면 처리 시간 또는 메모리 사용이 비례해서(선형적으로) 증가해요. 일반적인 for loop 가 그 예 입니다.

 

void sum(List <int> nums) {
    int result = 0;
    for(int i=0; i<nums.count; ++i){
    	result += nums[i];
    }
    return result;
}

• 알고리즘 : 순차 탐색

 

 

  O(N log N) : 선형 로그시간 (Log-Linear)     🟥🟥

로그 함수가 사용되기는 했지만, O(log₂N) 와는 비교할 수 없을 정도로 수행 시간이 큽니다. O(N) 알고리즘보다 훨씬 수행 시간이 크지요.

선형 로그 시간을 따르는 알고리즘의 복잡도는 로그 시간 복잡도와 선형 시간 복잡도를 곱한 만큼 커져요. 로그 시간으로 실행되는 알고리즘 O(log n) 을 n 번 반복하는 형태를 말해요.

• 알고리즘 : 병합 정렬, 퀵 정렬

 

 

  O(N^2) : 2차 시간 (Quadratic Time Complexity)   🩷🩷

반복문이 두 번 있는 케이스 흔히 이중(더블) 루프, doble for loop 라고 이야기하는 경우에요. 이 유형은 이중 루프 내에서 입력 자료를 처리하는 경우에 나타나요. N값이 큰 값이 되면 실행 시간을 감당하지 못할 정도로 커지죠.

 

const numbers = [1, 2, 3, 4, 5];

for (let i of numbers) {
    for (let j of numbers) {
        const x = i * j;
        console.log(x);
    }
}

• 알고리즘 : 버블 정렬, 삽입 정렬

 

이 알고리즘은 숫자 리스트 numbers 에 들어 있는 모든 숫자를 서로 곱해 변수에 저장한 후 출력합니다. 여기서 n은 numbers 리스트의 크기이므로, 이 알고리즘의 시간 복잡도 f(n) 은 다음과 같이 나타낼 수 있어요

f(n) = 1 + n * n * (1 + 1)

 

 

이 식의 (1 + 1) 부분은 (i * j) 를 변수 x 에 저장하는 단계와 console 에 해당합니다. 두 번 중첩된 for 루프를 통해 곱셈과 출력을 n * n 번 반복합니다. f(n) 은 다음과 같이 단순화 할 수 있어요.

f(n) = 1 + (1 + 1) * n**2

 

 

한 번 더 단순화 하면,

f(n) = 1 + 2 * n**2

 

마찬가지로 f(n) 의 크기를 지배하는 부분이 n**2 이므로 빅O표기법으로는

O(n) = n**2

 

 

 

 

  O(N^3) : 3차 시간 (Cubic)  

이 유형은 앞의 유형과 비슷하게 입력 자료를 삼중 루프 내에서 처리하는 경우에 나타나요. n의 세제곱에 정비례해요.

 

const numbers = [1, 2, 3, 4, 5];

for (let i of numbers) {
    for (let j of numbers) {
    	for (let k of numbers) {
        	const x = i + j + k;
        	console.log(x);
        }
    }
}

• 알고리즘 : 행렬 곱셈

 

이 알고리즘의 f(n) 은

f(n) = 1 + n * n * n * (1 + 1)

 

단순화 하면,

f(n) = 1 + 2 * n**3

 

 

2차 시간 복잡도와 마찬가지로 f(n)에서 가장 중요한 부분은 n**3 입니다. n**3 은 급격하게 커지기 때문에 만약 f(n)의 나머지 부분에 n**2 가 포함되어 있더라도 무시할 수 있을 정도에요.

빅오표기법에서는 아래와 같이 표현합니다.

O(n) = n**3

 

 

 

 

  O(2^n) : Cubic, O(N!) 등등  

입력자료의 수가 늘어남에 따라 급격히 실행 시간이 늘어나요. 

n번 반복할 수록 2의 n제곱만큼 시간이 증가함을 의미해요. n의 값이 10일 때 처리 시간이 10초가 걸렸다면 n의 값이 20일 경우 처리 시간이 10x 2^10초 필요하게 됨을 의미합니다.

주로 재귀로 구현하는 피보나치 수열이 O(2^n)의 시간 복잡도를 가집니다.

 

 

 

 

 

 

 

 

 

공간 복잡도 Space Complexity

---

알고리즘의 효율을 생각할 때는 컴퓨터의 메모리도 유한한 자원이므로 시간 복잡도뿐만 아니라 자원을 얼마나 사용하는지도 고려해야 해요. 공간 복잡도(Space Complexity)는 알고리즘의 실행을 완료할 때까지 필요한 자원의 양, 즉 고정 공간, 데이터 구조 공간, 임시 공간의 메모리를 얼마나 사용하는지 나타냅니다.

고정 공간(Fixed Space)은 프로그램 자체가 차지하는 메모리를 말하며,

자료구조 공간(Data Structure Space)은 데이터 세트, 예를 들어 탐색의 대상이 되는 리스트를 저장하는 데 필요한 메모리를 말해요.

알고리즘에서 이 데이터를 저장하기 위해 사용하는 메모리는 n의 크기에 따라 달라지게 되죠. 

 

또한 임시 공간(Temporary Space)은 알고리즘에서 중간 처리를 위해 사용하는 메모리, 예를 들어 데이터 전송을 위해 임시로 리스트 사본을 만들 때 필요한 메모리를 말해요.

 

앞서 살펴본 시간 복잡도의 개념을 공간 복잡도에도 적용할 수 있습니다. n의 팩토리얼(factorial)(n 이하의 양의 정수를 모두 곱한 값)을 계산하는 알고리즘은 상수 공간 복잡도인 O(1)을 따릅니다.

let x = 1;
const n = 5;

for (let i = 1; i <= n; i++) {
    x = x * i;
}

console.log(x);

 

이 알고리즘의 공간 복잡도가 상수인 이유는 n이 커져도 알고리즘에서 추가로 메모리를 사용하지 않기 때문입니다. 반면에 n까지 도달하면서 계산한 중간 결과를 모두 리스트에 저장한다면 이 알고리즘은 선형 공간 복잡도 O(n)을 따릅니다.

let x = 1;
const n = 5;
const aList = [];

for (let i = 1; i <= n; i++) {
    aList.push(x);
    x = x * i;
}

console.log(aList);

 

알고리즘에 필요한 공간 역시 n이 커지는 것과 같은 비율로 커지므로 이 알고리즘의 공간 복잡도가 O(n)이 됩니다. 시간 복잡도와 마찬가지로 알고리즘의 공간 복잡도 역시 상황에 따라 달라지지만 일반적으로는 공간을 적게 쓸수록 좋습니다.

 

 

 

 

 

 

 

---

 ⚡️⚡️

 

 

1. Big-O, Big-Theta, Big-Omega에 대해 설명해보시오

Big-O, Big-Theta, Big-Omega는 알고리즘의 성능을 수학적으로 표현하는 방법이에요.

• Big-O는 최악의 경우, 즉 알고리즘이 얼마나 느려질 수 있는지를 나타내요.
• Big-Theta는 평균적인 경우를 의미하며, 알고리즘의 실행 시간이 특정 범위 안에서 움직이는 것을 보여줍니다.
• Big-Omega는 최선의 경우, 즉 알고리즘이 최소 얼마나 빠르게 작동할 수 있는지를 나타내요.
  쉽게 말해, 알고리즘의 최선, 최악, 평균 성능을 이해하고 비교하는 기준입니다.

---

2. 다른 것을 사용하지 않고 Big-O를 사용하는 이유가 있을까요?

Big-O는 알고리즘의 성능을 직관적이고 간단하게 비교할 수 있게 해줘요. 최악의 경우를 기준으로 하기 때문에, 안정적인 시스템 설계를 위해 안전한 선택을 가능하게 합니다. 다른 복잡한 수학적 표현보다 명확하고 쉽게 커뮤니케이션할 수 있어, 개발자들 사이에서 표준처럼 사용됩니다.

---

3. O(1)은 O(N²)보다 무조건적으로 빠른가요?

아니요, 항상 그런 것은 아닙니다. O(1)은 "입력 크기에 상관없이 일정한 시간"을 의미하고, O(N²)은 "입력 크기에 따라 시간이 증가"한다는 뜻이에요.
하지만 실제로는 데이터 크기, 상수 시간의 크기 등이 영향을 미칠 수 있어요. 예를 들어 O(1)의 작업이 복잡한 연산이라면, 작은 입력에서는 O(N²)가 더 빠를 수도 있습니다. 빅오는 이론적인 성능 분석이기 때문에, 실제 성능은 구현과 환경에 따라 다를 수 있습니다.

 

 

 

 

 

 

 

출처 : https://www.hanbit.co.kr/channel/category/category_view.html?cms_code=CMS7965376216