자료구조(1) 시간복잡도 & 공간복잡도

자료구조란?

• 효율적으로 데이터를 관리하고 수정, 삭제, 탐색, 저장할 수 있는 데이터 집합

시간 복잡도

• 시간 복잡도란 문제를 해결하는 데 걸리는 시간과 입력의 함수 관계를 가리킵니다.
• 어떠한 알고리즘의 로직이 얼마나 오랜시간이 걸리는지를 나타내는데 쓰이며, 보통 빅오 표기법으로 나타냅니다.

빅오 표기법

• 입력 범위 n을 기준으로 해서 로직이 몇 번 반복되는지 나타내는 것
• 표기법
  • 시간 복잡도를 각각 최악, 최선, 중간(평균)의 경우에 대하여 나타내는 방법
  • Big-O(빅-오) ⇒ 상한 점근
  • Big-Ω(빅-오메가) ⇒ 하한 점근
  • Big-θ(빅-세타) ⇒ 그 둘의 평균.
• 가장 영향을 많이 끼치는 항의 상수인자를 빼고 나머지항을 없앤다.
• 입력 크기가 커질수록 연산량이 가장 많이 커지는 항만 신경쓰고 다른것은 그에 비해 미미하기 때문에 이것만 신경쓰면 된다는 이론
• 효율적인 코드로 개선하는 데 쓰이는 척도가 된다.

공간 복잡도

• 프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양
• 정적변수로 선언된 것 말고도 동적으로 재귀적인 함수로 인해 공간을 계속해서 필요로 하는 경우도 포함