c++ - 使用指针计算堆栈问题的大 O 表示法

Question

嗨，谁能帮我用大 O 表示法计算这段代码的算法复杂度？我不太了解使用 Big O，因为这段代码中有很多指针。我只知道一些代码。就像 cout 是 O(1)。其余的我不明白。我只是编程的初学者。请帮我算一下大o符号。谢谢。

#include <iostream>
#include <string>
#include <stdlib.h>

using namespace std;

class Book {
    int year, page;
    unsigned long long int code;
    string language, name, title;
    Book *head, *next, *prev, *link;

public:
    Book (string & name, string & title, unsigned long long int code, string & language, int year, int page) {
        head = NULL;
        this->name = name;
        this->title = title;
        this->language = language;
        this->code = code;
        this->year = year;
        this->page = page;
    }

    ~Book (void) {
        delete head;
    }

    void display (void);
    void add (void);
    void dellete (void);
};

void Book::add(void) {
    string name, title, language;
    int year, page;
    unsigned long long int code;
    cout << "Add a book...";
    cout << endl << "Author\t\t:", cin >> name;
    cout << "Title\t\t:", cin >> title;
    cout << "ISBN(13 digits)\t:", cin >> code;
    cout << "Language\t:", cin >> language;
    cout << "Year\t\t:", cin >> year;
    cout << "Pages\t\t:", cin >> page;

    Book* p = new Book(name, title, code, language, year, page);
    p->next = head;
    head = p;
}

void Book::dellete(void) {
    string name, title, language;
    int year, page;
    unsigned long long int code;
    Book* p, *prev, *next;

    if(head==NULL) {
        cout << "There is no book in the stack\n";
    } else if(head->next==NULL) {
        p = head;
        head = NULL;
        free(p);
        cout << "All book has been taken. Now the stack is empty\n";
    } else{
        p = head;
        head = p->next;
        free(p);
        cout << "A book has been taken\n";
    }
}

void Book::display(void) {
    Book* p = head;
    cout << "Displaying book(s)...\n";
    while (p) {
        cout << "----------------------------- \n";
        cout << "Author\t\t:" << p->name << endl;
        cout << "Title\t\t:" << p->title << endl;
        cout << "ISBN\t\t:" << p->code << endl;
        cout << "Language\t:" << p->language << endl;
        cout << "Year\t\t:" << p->year << endl;
        cout << "Pages\t\t:" << p->page << endl;
        cout << endl;
        p = p->next;
    }
}

int main (int argc, char const** argv) {
    string blank = "";
    Book* B = new Book(blank, blank, 0, blank, 0, 0);
    int opt;
    for (;;) {
        cout << "----------------------------- \n";
        cout << "1) Add a book.\n";
        cout << "2) Show all books.\n";
        cout << "3) Take a book\n";
        cout << "4) Exit. \n";
        cout << "Don't use space but use underscore...\n\n";

        cout << "Options:", cin >> opt;
        switch (opt) {
            case 1:
                B->add();
                break;
            case 2:
                B->display();
                break;
            case 3:
                B->dellete();
                break;
            case 4:
                exit(0);
            default:
                continue;
        }
    }
    return 0;
}

Answer 1

O-Notation 根据问题的大小，根据算法的复杂程度(例如运行时或内存使用情况)对算法进行分类。所以 O(1) 意味着无论问题有多大，算法的复杂度都不会增加，无论这个常数成本有多大。

让我们看一下您的一些程序部分。

删除

这具有 O(1) 的运行时复杂度，因为无论 Books 堆栈有多大，删除书顶的操作量总是几乎相同堆。唯一的区别在于 0、1 和 2 本书之间，但是如果您将堆栈增长到无穷大，则操作量不会增长，这才是最重要的。

添加

这里很难衡量。由于此方法一次只添加 1 本书，所以它是 O(1)，因为无论已经有多少本书(这是唯一的可变大小)，您始终需要相同数量的操作。如果您允许一次添加多本书会更有趣。

显示

因此 display 打印出堆栈中的所有书籍。如果你增加书籍的数量，操作的数量也会增加。现在的问题是以什么方式？在这种情况下，书籍数量加倍会使说明数量加倍。这是线性增长，因此复杂度等级为 O(n)。

---

查看循环计数会很有帮助。问题大小的一个循环通常确实意味着 O(n)。如果您有两个嵌套循环(超过问题大小)，您通常会有 O(n²) 等等。

关于你的问题，你的 main 函数中的死循环是什么，这取决于你定义的问题大小，我不知道在这里衡量它是否有意义。

如果您将用户操作总数定义为问题大小，事情就会变得复杂。如果我们把显示部分放出来，只允许添加和删除，它是 O(n)，因为一切都是常量(因为添加和删除是 O(1)，其他东西是独立的指令，如 cout)，它们发生在基于问题大小 n(用户操作的数量)的循环。如果将显示考虑在内，事情就没那么简单了，因为显示的复杂度为 O(m)(m = 书籍数量)，这在很大程度上取决于之前给出的实际用户输入。我不知道那里会有什么复杂性。