o(n)

12장 동적 프로그래밍

지금까지 재귀적으로 작성하는 법과 재귀로 보다 복잡한 문제를 해결하는 법을 배웠지만 재귀로 확실히 어떤 문제는 해결할 수 있어도 제대로 사용하지 않으면 또 다른 문제가 발생한다. 재귀는 종종 O(2ⁿ)같은 가장 느린 빅 오 카테고리의 주된 요인이 된다. 12.1 불필요한 재귀 호출 다음의 재귀 함수는 배열의 최대값을 찾는다. function max(array) { if (array.length === 1) return array[0]; if (array[0] > max(array.slice(1))) { return array[0]; } else { return max(array.slice(1)); } } 만약 배열의 요소가 하나면 그 값이 최대값이 된다. 각 재귀 호출의 핵심은 하나의 수 (array[0..