TIL Day56 시간 복잡도/ 공간 복잡도

- 시간복잡도와 공간복잡도가 무엇일까?

• 시간 복잡도란
  - 특정 크기의 입력을 기준으로 할 때 필요한 연산의 횟수를 나타냅니다. 시간 복잡도에는 빅오 표기법이라는 복잡도를 나타내는 점근 표기법 중 가장 많이 사용되는 표기법을 사용합니다.
  - Big O 표기법(Big O Notation)이란?
  Big O란 연산 횟수의 함수 T(n) 의 최고차항의 차수에 O를 씌운 표기법이다. 아래와 같이 표기하면 된다.빅오의 순서는 아래와 같으며, 커질 수록 연산 횟수가 더 많다는 뜻이며, 연산에 더 오랜 시간이 걸린다는 뜻이다. 화공과에서 수학을 배울 때 배우던 내용과 비슷하다.
  
  

• 공간 복잡도는
  • 프로그램 실행과 완료에 얼마나 많은 공간(메모리)가 필요한지를 나타냅니다. 알고리즘을 실행시키기 위해 필요한 공간, 고정 공간과 가변 공간이 있습니다.