알고리즘 복잡성에 대한 간단한 작업에 대한 솔루션

그래서 여기에 해결책이 있습니다. 읽기 쉽게 질문을 반복합니다

매우 나쁜 피보나치 구현을 소개하겠습니다.

function fib(n) {
    if (n <= 1) {
        return 1
    }
    return fib(n - 2) + fib(n - 1)
}

첫 번째 질문은 매우 간단합니다.

Q1. What's wrong with this implementation and how to fix it?

대답

구현은 하나의 숫자를 여러 번 다시 계산하여 불필요한 작업을 많이 만듭니다. 보다 효율적인 구현은 단순합니다for -루프:

function betterFib(n) {
    let r1 = 1;
    let r2 = 1;
    for (let i = 2; i <= n; i++) {
        const _r2 = r2;
        r2 = += r1;
        r1 = _r2;
    }
    return r2;
}

이것은 "기능적으로 순수"하지 않으며 멋지게 번역된 수학 공식처럼 보이지 않습니다. 그러나 그것은 빨리 작동합니다!

Q2. What's it complexity in terms of ? How to estimate and prove it?

대답

기하 급수적입니다. 그러나 정확하게는 보이지 않는다.

O(2n)O(2^n)O(2n)

모든 호출이 2개의 재귀 호출을 생성하는 것은 아니며 "왼쪽"재귀 호출fib(n - 2)이 "오른쪽"재귀 호출보다 빠르게 재귀 기반에 도달하기 때문입니다. 호출 트리를 스케치해 봅시다.



로 그린 Sketchpad

기하급수적으로 변이 같지 않은 멋진 그림처럼 보입니다 😄 그리고 작업은 "면적"을 계산하는 것과 같습니다. 정확하게 계산하는 쉬운 방법이 있는지 잘 모르겠지만 경계를 추정하는 것은 가능합니다!

측면이 동일하고 그림 높이가 원래 그림의 왼쪽 높이와 같으면 결과 영역은 다음과 같습니다.

O(2n/2)O(2^{n/2})O(2n/2)

변이 동일하고 그림 높이가 원래 그림의 오른쪽 높이와 같으면 결과 영역은 다음과 같습니다.

O(2n)O(2^n)O(2n)

그리고 그것이 답입니다! 복잡성

트리플 엑스

원래 함수fib는 다음 간격 내에 있습니다.

O(2n/2)


이 솔루션을 읽어 주셔서 감사합니다. 문제 설명이 포함된 게시물을 읽으셨다면 두 배로 감사드립니다. 시도해 보신 경우 세 배로 감사드립니다! 이런 종류의 내용이 흥미롭다면 피드백을 남겨주세요. 그러면 저는 계속해서 짧고 재미있는 프로그래밍 실습을 게시할 것입니다. 감사합니다 🙏