공간복잡도

[자료구조] 5.1. 복잡도

본 포스팅은 [면접을 위한 CS 전공지식 노트]의 내용을 참고하여 작성하였습니다. 5.1. 복잡도 복잡도는 시간 복잡도와 공간 복잡도로 나뉜다. 1) 시간 복잡도 문제를 해결하는 데 걸리는 시간과 입력의 함수 관계. 알고리즘의 로직이 얼마나 오랜 시간 걸리는지. 빅오 표기법*으로 나타냄. (빅오 표기법*: 가장 영향을 많이 끼치는 항의 상수 인자와 나머지 항을 없앤 것. 예를 들어 10n^2+n의 시간이면 O(n^2)로 표기한다.) 필요한 이유: 효율적인 코드로 개선하는 데 쓰이는 척도. 2) 공간 복잡도 프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양. 정적 변수는 물론이고 재귀함수로 인해 동적인 공간을 계속해서 필요할 경우도 포함. int a[1005]; 위와 같은 코드를 예시로 들면, a 배열..