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

시간 복잡도(Time Complexity)

시간 복잡도는 알고리즘이 주어진 입력 크기에 대해 실행되는 데 걸리는 시간을 측정하는 방법 중 하나 주로 주요 로직의 반복 횟수를 중점으로 측정되며, 컴퓨터 사양 등 여러 요소에 영향을 받을 수 있다

console.time("test");
let sum = 0;
for (let i = 0; i < 1000000; i++) {
  sum += 1;
}
console.timeEnd("test");
// test: 1.575ms

• 이러한 시간 측정은 컴퓨터의 성능 등에 영향을 받으므로, 알고리즘의 성능을 설명할 때는 주로 입력 크기에 따른 알고리즘의 동작을 중점으로 복잡도를 정한다

빅오표기법 (Big O Notation)

빅오표기법은 알고리즘의 성능을 나타내는 데에 사용되는 표기법 중 하나. 가장 영향을 많이 미치는 항의 1. 상수 인자를 제거하고 2. 나머지 항을 없애서 복잡도를 나타낸다

for(int i = 0; i < 10; i++){  // 10번
    for(int j =0; j < n; j++){  //n번
        for(int k = 0; k < n; k++){  //n번
            if(true) cout << k << '\n';  //단순한 로직
        }
    }
}
for(int i = 0; i < n; i++){ // n번
    if(true) cout << i << '\n';
}

• 위 코드의 시간 복잡도는 10n^2 + n이므로 빅오표기법으로는 O(n^2).
• 시간 복잡도 비교 n! > 2^n > n^2 > nlogn > n > logn > 1
  

상수시간 시간 복잡도 O(1)

• 상수시간은 입력 크기와 상관없이 일정한 시간 복잡도를 가지는 것을 의미.
• O(1)로 표현
• 예시: 간단한 연산, 배열의 인덱스 참조

시간 복잡도가 필요한 이유

시간 복잡도는 주로 효율적인 코드로 개선하는 데 기준이 된다.

• 예를 들어, O(n^2)의 알고리즘을 O(n)으로 개선하면 성능적인 향상

공간 복잡도(Space Complexity)

공간 복잡도는 알고리즘이 실행되는 동안 필요한 메모리 공간의 양. 정적 및 동적 변수, 배열, 맵 등이 포함됨

int a[10000000];
void f(){
    int b[1004];
}
int main(){
}

• 위 코드의 공간 복잡도는 10000000 * 4바이트 + 1004 * 4바이트
• 만약 입력 N이고 이를 N개짜리 int형 요소를 담는 배열로 선언했다면, 4*N바이트의 공간이 필요 int[N]; -> O(N), 공간 복잡도 4*N
• 공간 복잡도는 주로 "문제의 최대 범위"나 "제한된 메모리"에 기반하여 결정됩니다.
  • 예시: 메모리 제한 512MB = 512000000byte = int a[128000000] 까지 선언 가능

REF