시간복잡도와 공간복잡도

정의

• 시간복잡도와 공간복잡도는 알고리즘의 성능을 평가하는 방법 입니다.

시간복잡도 vs 공간복잡도

• 공간복잡도보다 시간복잡도를 더 우선해서 생각합니다.

시간복잡도

정의

• 시간복잡도는 컴퓨터 프로그램의 입력값과 연산 수행 시간의 상관관계를 나타내는 척도입니다.
• 시간복잡도는 알고리즘이 문제를 해결하는 데 걸리는 시간을 분석한 결과입니다.
• 시간 복잡도는 알고리즘의 절대적인 실행 시간이 아닌 알고리즘 수행에 필요한 연산 횟수를 나타냅니다. (연산의 종류는 산술, 대입, 비교, 이동을 말합니다)

빅오(big-O) 표기법

• 시간복잡도를 계산하는 대표적인 방법입니다.
• 빅오 표기법은 데이터 n개를 처리하는 시간을 n의 가장 큰 차수로 표현합니다.
• 다음은 빅오 표기법의 규칙을 이해할 수 있는 예시들입니다.
  $n$개의 데이터를 처리하는 데 $2n$시간이 걸렸다 -> $O(n)$
  $n$개의 데이터를 처리하는 데 $2n^2+10n$시간이 걸렸다 -> $O(n^2)$
  $n$개의 데이터를 처리하는 데 $n$과 상관없이 일정한 시간이 걸렸다 -> $O(1)$
  -> 빅오 표기법은 상수시간을 무시합니다.
  -> 빅오 표기법은 n의 차수가 가장 큰 숫자로만 표현합니다.

빅오 표기법은 최악의 경우를 가정합니다.

• 전체 길이가 N인 배열에서 A의 값이 어디 있는지 찾아야 합니다. 하나의 값을 확인하는 데 걸리는 시간이 1초라고 가정했을 때 A가 가장 앞에 있다면 해당 문제는 1초만에 해결됩니다. 하지만 그렇다고 선형 탐색을 O(1)로 표현하지 않습니다. 이처럼 시간복잡도는 최선,평균,최악중 최악의 경우로 시간복잡도를 평가합니다.

공간복잡도

정의

• 공간복잡도는 프로그램을 실행시킨 후 완료하는 데 필요로 하는 자원 공간의 양이 얼마인지를 나타냅니다.
• 공간복잡도는 알고리즘이 문제를 해결하는 데 필요한 메모리 공간을 분석한 결과입니다.

계산

• 총 필요한 저장 공간 = 고정 공간 + 가변 공간 입니다.

  • 고정 공간: 알고리즘과 무관한 공간입니다.(ex-코드 저장 공간, 단순 변수 및 상수를 저장한 공간
  • 가변 공간: 알고리즘을 실행하면서 동적으로 필요한 공간

  -> 공간복잡도는 가변 공간에 큰 영향을 받게 됩니다.

References

• https://madplay.github.io/post/time-complexity-space-complexity
• https://yoongrammer.tistory.com/79
• https://ledgku.tistory.com/33