Chuỗi Fibonacci

Oct 13 2020

Tôi đang gặp khó khăn với phân tích thời gian và độ phức tạp. Tôi đã thực hiện một chuỗi fibonacci theo cách đệ quy. Tôi nghĩ đó là O (n ² ) . Bạn có thể tìm ra phân tích thời gian? Nếu có thể, bạn có thể giải thích nó?

#include<iostream>
using namespace std;

void fibonacci(int n,int n1,int n2)
{
    if(n==0)
    {
        cout<<endl<<n1;
        return;
    }
    else if(n==1)
    {
        cout<<endl<<n2;
        return;
    }
    fibonacci(n-1,n2,n1+n2);
    return;
}

int main()
{
    int n;
    cout<<"Enter the number:"<<endl;
    cin>>n;
    fibonacci(n,0,1);
    return 0;
}

Trả lời

7 TheodoreNorvell Oct 14 2020 at 00:25

Tôi không chắc bất kỳ câu trả lời nào thực sự giải quyết được sự phức tạp. Tôi sẽ làm điều đó bằng cách chuyển đổi thuật toán của bạn thành một thuật toán đơn giản hơn mà không làm thay đổi độ phức tạp về thời gian. Điều này vừa chứng minh độ phức tạp về thời gian, vừa cung cấp cho bạn một phiên bản của thuật toán có thể dễ đọc và dễ suy luận hơn.

Hãy bắt đầu với giải pháp của bạn

void fibonacci(int n,int n1,int n2)
{
    if(n==0)
    {
        cout<<endl<<n1;
        return;
    }
    else if(n==1)
    {
        cout<<endl<<n2;
        return;
    }
    fibonacci(n-1,n2,n1+n2);
    return;
}

Phần else ifkhông thực sự cần thiết, vì vậy hãy xóa phần đó và cũng loại bỏ các returnlệnh thừa . [Xem các bình luận để thảo luận về lý do tại sao bước này không hoàn toàn vô tội như nó có vẻ.]

void fibonacci(int n,int n1,int n2)
{
    if(n==0) {
        cout<<endl<<n1; }
    else { 
        fibonacci(n-1,n2,n1+n2); }
}

Đảo ngược if. Ngoài ra, tôi sẽ đặt lại một trong những thứ đó returnvà lấy bản in ra khỏi elsephần.

void fibonacci(int n,int n1,int n2)
{
    if(n!=0) {
        fibonacci(n-1,n2,n1+n2);
        return ; }
    cout<<endl<<n1;
}

Áp dụng tối ưu hóa đệ quy đuôi --- nghĩa là thay thế lệnh gọi đệ quy và lệnh trả về sau bằng phép gán lại các tham số và một bước nhảy đến đầu chương trình con. Bước này sẽ thay đổi độ phức tạp của không gian, * nhưng không thay đổi độ phức tạp về thời gian.

void fibonacci(int n,int n1,int n2)
{
    start: 
    if(n!=0) {
        int sum = n1+n2 ;
        n1 = n2 ;
        n2 = sum ;
        n = n-1 ;
        goto start ; }
    out<<endl<<n1;
}

Sử dụng một vòng lặp thay vì a goto.

void fibonacci(int n,int n1,int n2)
{
    while(n!=0) {
        int sum = n1+n2 ;
        n1 = n2 ;
        n2 = sum ;
        n = n-1 ; }
    cout<<endl<<n1;
}

Bạn không thực sự cần tham số là tham số. Tôi có thể ghi lại chương trình con, vì vậy nó rõ ràng là gì. Và tôi sẽ ghi lại vòng lặp while với một bất biến, vì vậy nó rõ ràng hơn về cách hoạt động của nó.

void fibonacci(int n)
// Precondition: n >= 0
// Postcondition: the value of fib(n) has been printed to standard out
//                preceded by an end of line.
{
    int n1 = 0 ;
    int n2 = 1 ;
    // Let n0 be the original value if n.
    // invariant n1 == fib( n0-n ) and n1 == fib(n0-n+1) 
    while(n!=0) {
        int sum = n1+n2 ;
        n1 = n2 ;
        n2 = sum ;
        n = n-1 ; }
    cout<<endl<<n1;
}

(Và cũng có thể thay đổi nơi gọi của nó.)

Tại thời điểm này, rõ ràng (tôi nghĩ) rằng thuật toán là O (n). Không có phép biến đổi nào làm thay đổi độ phức tạp về thời gian, do đó độ phức tạp về thời gian của phép biến đổi ban đầu cũng là O (n).

(*) Nghĩa là, nó sẽ thay đổi độ phức tạp không gian từ O (n) thành O (1) trừ khi trình biên dịch của bạn thực hiện tối ưu hóa đệ quy đuôi. Nếu có, độ phức tạp không gian là O (1) ngay từ đầu.

14 AryanParekh Oct 13 2020 at 11:04

Trong khoảng `using namespace std`

Bạn nên cố gắng tránh câu nói này vì nó được coi là hành vi xấu . Tốt nhất là nên tránh nó bất cứ khi nào bạn có thể. Đây là một ví dụ đơn giản tại sao.

#include <iostream>
#inlcude <list>

using namespace std;

class list // uh-hoh, list is already defined, or is that std::list?
{     
    ...
};

Một vấn đề khác là nếu bạn có cái này trong bất kỳ tệp tiêu đề nào trong dự án của mình, bạn sẽ buộc phải sử dụng tệp này trong bất kỳ tệp nào bạn đã bao gồm tiêu đề.

Tại sao sử dụng không gian tên std được coi là hành vi xấu

Lập trình meta mẫu

Điều này chuyển phép tính từ thời gian chạy sang thời gian biên dịch . Chương trình của bạn sẽ mất nhiều thời gian hơn để biên dịch, nhưng độ phức tạp sẽ rất cao O(1). Nó sử dụng các mẫu trong C ++ để buộc trình biên dịch tính toán giá trị.

Đây là một lựa chọn khác để tiếp cận vấn đề này và là cách nhanh nhất vì điều này chuyển phép tính sang thời gian biên dịch .

Tuy nhiên, hạn chế là bạn không thể sử dụng các giá trị không được biết tại thời điểm biên dịch. Ví dụ: bạn có thể tìm thấy giá trị 5nhưng không phải thứ gì đó mà người dùng sẽ nhập hoặc ví dụ: một số ngẫu nhiên được tạo.

#include<iostream>

template <unsigned N>
struct Fibonacci
{
    enum : uint64_t
    {
        value = Fibonacci<N-1>::value + Fibonacci<N-2>::value
    };
};

template <>
struct Fibonacci<1>
{
    enum
    {
        value = 1
    };
};

template <>
struct Fibonacci<0>
{
    enum
    {
        value = 0
    };
};

int main()
{
    std::cout << Fibonacci<20>::value;
}

Phương pháp này sẽ nhanh nhất nhưng sẽ chỉ hoạt động nếu số của bạn không đổi.
Lập trình meta mẫu trong C ++

Thay thế đệ quy bằng lặp lại

Mặc dù đệ quy làm cho mã của bạn sạch hơn một chút, nhưng đệ quy hầu như luôn chạy chậm hơn , điều này là do đối với mỗi lệnh gọi, nó cần phân bổ một khung ngăn xếp mới
Do thực tế là không gian trong ngăn xếp là hữu hạn , có giới hạn về số lượng lệnh gọi đệ quy bạn có thể tạo, trước khi C ++ cung cấp cho bạn 0xC00000FD. Đó là tràn ngăn xếp
Với một vài dòng mã nữa, bạn có thể thay thế đệ quy bằng kịch bản này và làm cho nó nhanh hơn nhiều mà không gặp vấn đề này.
Điều này không có nghĩa là bạn không nên sử dụng đệ quy, một số thuật toán cần đệ quy, nhưng nếu bạn có thể thay thế nó bằng phép lặp, thì nó đáng giá.

Đây là với sự lặp lại.

uint64_t fibonacci(int n)
{
    uint64_t n1 = 0,n2 = 1,n3 = 1;
    if (n == 1 || n == 0) return 0;
    else if(n == 2) return 1;

    for (int i = 2;i < n;++i)
    {
        n3 = n1 + n2;
        n1 = n2;
        n2 = n3;
    }
    return n3;
}

`'\n'` kết thúc `std::endl`

'\n'và std::endlcả hai sẽ hoàn thành nhiệm vụ của bạn, nhưng mọi lần std::endlgọi std::flushvà xóa luồng, đây là lý do tại sao nó sẽ chậm hơn, đơn giản là in'\n'

So sánh giữa std :: endl và '\ n'

7 MartinYork Oct 13 2020 at 13:34

Cách rõ ràng nhất để viết fib:

int fib(int n)
{
    if (n < 2) // 0 or 1
    {
        return 1;
    }
    return fib(n-1) + fib(n-2);
}

Bạn có thể thấy nó bùng nổ vì với mỗi cuộc gọi đến fib (), bạn nhận được 2 cuộc gọi tiếp theo, cả hai đều nhận được 2 cuộc gọi và tất cả đều nhận được 2 cuộc gọi, v.v.

      Level               Calls                 Calls  This Level    Total Calls
    Level n                   1                        1                 1
    Level n-1            1         1                   2                 3
    Level n-2          1   1      1   1                4                 7
    Level n-3         1 1 1 1    1 1 1 1               8                 15

Vì vậy, độ phức tạp của Fib là Fib !!!!!
Chính xác hơn Hoàn thành là O(2Fib(n)-1)
nhưng loại bỏ các hằng sốO(Fib(n))

Hãy viết một số mã để xác thực điều này:

int fibComplexity(int n)
{
     // has the same properties of fib.
     // but returns the number of calls rather than the value.
     if (n < 2)
     {
         return 1;      // You called this function once.
     }
     return 1           // the call to this function.
            + fibComplexity(n-1)  // Count of calls in this tree
            + fibComplexity(n-2)  // Count of calls in this tree.
}

Nếu chúng ta chạy điều này:

int main()
{
    for(int loop = 2; loop < 15; ++loop)
    {
        std::cout << loop << " " << fib(loop) << " " << fibComplexity(loop) << "\n";
    }
}

Tạo: (thêm định dạng)

n  F   O
2  2   3     
3  3   5
4  5   9
5  8   15
6  13  25
7  21  41
8  34  67
9  55  109
10 89  177
11 144 287
12 233 465
13 377 753
14 610 1219   O = 2f-1

Nhưng mỗi khóa học lập trình bạn tham gia sau đó sẽ yêu cầu bạn thực hiện một giải pháp dựa trên tuyến tính.

Những gì bạn trình bày ở trên là một giải pháp đệ quy (nhưng tuyến tính). Hầu hết mọi người sẽ đi tìm giải pháp tuyến tính dựa trên vòng lặp (nhưng không có sự khác biệt). Độ phức tạp hoàn toàn giống nhau.

Những gì bạn đã làm là gọi một cách đệ quy hàm thêm mọi thứ khi bạn thực hiện. Mỗi cuộc gọi thực hiện chính xác một cuộc gọi bổ sung nhưng chỉ đến độ sâu n. Sau đó, nó trở lại.

Vì vậy, bạn có độ phức tạp của O(n).

Nhưng bạn có thể tiến thêm một bước nữa. Thuật toán fib có thể dễ dàng được thực hiện như O(1).

Điều này là do fib nhanh chóng vượt quá kích thước của một số nguyên (thậm chí là dài). Bạn có thể dễ dàng tính toán trước tất cả các giá trị hợp lệ có thể được lưu trữ trong một biến và đặt chúng vào một mảng. Sau đó, chỉ cần trả về giá trị bằng cách tra cứu kết quả:

int fib(int n) {
    static const int fibValue[] = { ... };
    if (n < 0 || n > std::size(fibValue)) {
        // This is 47 for 32 bit ints
        //         93 for 64 bit ints
        throw "Result out of range"
    }
    return fibValue[n];
}

3 DavidG. Oct 14 2020 at 00:18

Nói một cách rõ ràng: Bạn là \$O(n)\$trong thời gian và \$O(n)\$trong trí nhớ. Tôi không tin rằng bạn có thể dễ dàng làm tốt hơn số học số nguyên (khi thực sự tính toán nó) trong thời gian, nhưng bộ nhớ có thể là \$O(1)\$.

Như đã được Peter Cordes chỉ ra , có một " Dạng đóng " cho dãy Fibonacci, có nghĩa là nếu bạn có một hệ thống dấu chấm động chính xác vô hạn thời gian không đổi, bạn có thể đạt được \$O(1)\$. Dấu phẩy động trên máy tính có thể đạt được giá trị gần đúng, nhưng tôi nghĩ bạn sẽ nhận được kết quả chính xác hơn với phép toán số nguyên.

Như Peter Cordes cũng đã chỉ ra , có một " phương pháp trình tự Lucas " có thể làm được \$O(\log{n})\$ đã cho phép nhân số nguyên và phức tạp hơn một chút.

Nếu bạn sử dụng lặp đi lặp lại hàm của mình để in dãy Fibonacci, kết quả thời gian của bạn sẽ là \$O(n^2)\$và điều đó có thể được thực hiện trong \$O(n)\$.