시간 복잡도와 공간 복잡도의 차이점

시간 복잡도와 공간 복잡도의 차이점?

●시간 복잡도와 공간 복잡도의 차이점?

• 하나의 문제를 해결하는 여러 알고리즘이 존재할 수 있으며 그리고, 개발자는 성능을 평가하여 하나를 결정해야 하며 이때, 코드가 실행될 때 걸리는 정확한 시간을 측정하는 방법으로 속도를 비교할 수 있지만, 실행 시간은 기계에 의존적이며 대안으로 나온 알고리즘들이 모두 짧은 시간 내로 수행되어 비교가 어려울 수 있음

• 이러한 경우, 직접 속도를 측정하는 것이 아닌 컴퓨터가 처리해야 하는 연산의 수를 세는 것이 나은 방법일 수 있으며 이러한 아이디어를 기반으로 특정 입력을 기준으로 개략적인 연산의 수를 계산한 것이 시간 복잡도(Time Complexity) 이며 반면, 공간 복잡도(Space Complexity) 는 특정 입력을 기준으로 알고리즘이 얼마나 많은 공간을 차지하는지를 다룸

• 정리하자면, 시간 복잡도와 공간 복잡도는 모두 알고리즘 평가의 척도로 사용될 수 있으며, 시간 복잡도는 개략적인 연산의 수를 기준으로 알고리즘 속도를 평가하는 척도로 사용되는 반면, 공간 복잡도는 알고리즘의 메모리 사용량을 평가하는 척도로 사용되는 것이 차이점임

●빅오 표기법은 무엇인가?

• 빅오 표기법은 복잡도를 표현하는 표기법 중 하나로 불필요한 상세를 무시하고 필수적인 부분에 집중하는 점근적 표기법을 따르며, 빅오 표기법은 O(n) 형식으로 어떤 함수의 입력 값에 따라 알고리즘의 실행 시간 및 공간 사용량이 어떻게 변하는지를 설명함

// n이 입력되면 n번 루프가 반복되므로, O(n)으로 표기합니다.
for (int i = 0; i < n; i++) { ... }

// 아래 루프는 O(n)으로 표기합니다. n이 무한에 가까울 수록 k가 의미가 없기 때문입니다. (상수항과 계수 무시)
int k = 5;
for (int i = 0; i < n * k; i++) { ... }

// 입력값인 n과 m이 독립적이라면 빅오는 더할 수 있습니다. O(n + m)으로 표기합니다.
for (int i = 0; i < n; i++) { ... }
for (int i = 0; i < m; i++) { ... }

// 빅오는 곱해질 수 있습니다. O(n^2)으로 표기합니다.
for (int i = 0; i < n; i++) {
  for (int j = 0; j < n * 5; j++) {}
}

// 가장 큰 항 외에는 무시할 수 있습니다. O(n^2)로 표기합니다.
for (int i = 0; i < n; i++) {}

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