알고리즘/이론

책 '코딩 인터뷰 완전 분석(게일 라크만 맥도웰)' 을 읽고 정리한 글입니다. big-O 시간의 상한. 상한 또는 평균을 의미한다. 대개는 상한을 의미하는데, 간혹가다가 평균을 의미할 때도 있다. 공간 복잡도 공간(메모리)을 얼마나 사용하느냐를 의미한다. 모든 변수들이 사용될 때 사용하는 메모리를 측정해야하는건가? 하는 혼선이 생길 수 있다. → No. 그런걸 얘기하지는 X 동시에 사용되는 메모리만 측정한다. 책에서는 factorial에 대한 예를 들었다. 호출될때마다 재귀가 되기 때문에, sum3을 실행될 시점에 sum4가 아직 끝나지 않음 콜 스택이 계속 쌓인다. 결국은, 공간이 가장 많이 사용되는 시점의 공간 복잡도가 얼마인지를 얘기하는 것. 예제 및 연습 문제 (책 69p) 예제 1. 같은 길이의..