[실압코] 시간복잡도 & 공간복잡도

 알고리즘의 효율성을 평가하는 두 가지 중요한 척도, 시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity)에 대해 알아보겠습니다.

시간복잡도

 시간 복잡도란 입력값의 크기에 따라 알고리즘의 수행 시간이 얼마나 변하는지를 나타내는 척도입니다. 즉, 입력 데이터가 늘어날수록 연산 횟수가 얼마나 증가하는지를 보여줍니다. 알고리즘의 성능은 주로 점근 표기법(Asymptotic Notation)을 사용해 표현합니다.

• 빅오(Big-O) 표기법 : O(n) : 알고리즘 성능의 상한(Worst-Case)을 나타내며, 가장 일반적으로 사용됩니다. "아무리 오래 걸려도 이 시간보다는 덜 걸린다"는 의미를 가집니다.
• 오메가(Ω) 표기법 : Ω(n) : 알고리즘 성능의 하한(Best-Case)을 나타냅니다.
• 세타(Θ) 표기법 : Θ(n) : 알고리즘 성능의 평균(Average-Case)을 나타냅니다.

 이 중 빅오(Big-O) 표기법이 가장 중요하게 다뤄지는 이유는, 우리는 알고리즘이 마주할 수 있는 최악의 상황에서도 제한 시간 내에 동작하는지를 보장해야 하기 때문입니다. 예를 들어, 어떤 알고리즘의 시간 복잡도가 O(n^2)이라면, 입력 크기가 n일 때 필요한 연산 횟수가 대략 n^2에 비례하여 증가한다는 의미입니다.

공간복잡도

 공간 복잡도란 입력값의 크기에 따라 알고리즘이 사용하는 메모리의 양이 얼마나 변하는지를 나타내는 척도입니다. 시간 복잡도와 마찬가지로, 주로 최악의 경우를 고려하는 빅오 표기법을 사용합니다. 예를 들어, 알고리즘의 공간 복잡도가 O(n)이라면 입력 크기 n에 비례하여 필요한 메모리 공간이 늘어난다는 뜻입니다. 만약 O(n^2)이라면, n×n 크기의 2차원 배열을 선언하는 경우를 생각할 수 있습니다.

알고리즘 문제 해결에서의 시간복잡도 & 공간 복잡도

 코딩 테스트나 알고리즘 대회에서는 보통 시간제한과 메모리 제한이 주어집니다. 이 제한은 "이 문제에는 반드시 이 제한을 만족하는 효율적인 풀이가 존재한다"는 중요한 힌트가 됩니다. 예를 들어, 다음과 같은 제한이 있다고 가정해 봅시다.

• 시간제한 : 2초
• 메모리 제한 : 128MB
• 입력 크기(N)의 최댓값 : 100,000

1. 시간 복잡도 분석

 일반적으로 1초에 약 1억 번의 연산이 가능하다고 어림잡아 계산합니다. 시간제한이 2초이므로, 우리는 약 2억 번 이내의 연산으로 문제를 해결해야 합니다.

• 만약 O(n^2) 알고리즘을 사용한다면?
  • 연산 횟수 : (100,000)^2 = 10,000,000,000 (100억) 번
  • 결과 : 2억 번을 훨씬 초과하므로 시간 초과가 발생합니다.
• 만약 O(nlogn) 알고리즘을 사용한다면?
  • 연산 횟수: 100,000 × log2​(100,000) ≈ 100,000 × 16.6 ≈ 1,660,000 (약 166만) 번
  • 결과: 2억 번 이내이므로 시간 내에 충분히 통과합니다.

2. 공간 복잡도 분석

 int 자료형이 4바이트라고 할 때, 128MB 메모리로는 약 3,200만 개(128 × 1024 × 1024 ÷ 4)의 int를 저장할 수 있습니다. 입력 크기가 10만 일 때 O(n) 복잡도로 10만 개의 int 배열을 사용하는 것은 문제가 없지만, O(n^2) 복잡도로 100,000 × 100,000 크기의 2차원 배열을 선언하는 것은 메모리 제한을 초과하게 됩니다.

 이처럼 문제에서 주어진 입력 크기 제한과 시간/메모리 제한을 먼저 확인하면, 내가 설계해야 할 알고리즘이 어느 정도의 복잡도를 가져야 하는지에 대한 명확한 가이드라인을 얻을 수 있습니다.