Вычисление обозначения Big O для задачи стека с использованием указателя - PullRequest
Новая
       16

Вычисление обозначения Big O для задачи стека с использованием указателя

0 голосов
/ 06 октября 2018

Привет, кто-нибудь может мне помочь подсчитать алгоритмическую сложность этого кода, используя обозначение Big O?Я не слишком разбираюсь в использовании Big O, потому что в этом коде много указателей.Я просто знаю немного кода.Как и Cout является O (1).Остальное я не понимаю.Я только начинающий в программировании.Пожалуйста, помогите мне посчитать большую букву.Спасибо. 

#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;
}

1 Ответ

0 голосов
/ 06 октября 2018

O-нотация классифицирует алгоритм по степени сложности (в смысле, например, времени выполнения или использования памяти) в зависимости от размера проблемы.Таким образом, O (1) означает, что независимо от того, насколько велика проблема, алгоритм не усложняется, независимо от того, насколько велика эта постоянная стоимость.

Давайте рассмотрим некоторые части вашей программы.

Удалить

Это имеет сложность во время выполнения O (1) , потому что независимо от размера стека книг, он всегда почти одинаковыйопераций, которые вы делаете для удаления верхней части стопки книг.Единственная разница между 0, 1 и 2 книгами, но если вы увеличиваете стек до бесконечности, количество операций не увеличивается, и это то, что имеет значение.

Add

Здесь сложно измерить.Поскольку этот метод добавляет только 1 книгу за раз, это O (1) , потому что независимо от того, сколько книг уже есть (это единственный переменный размер), вам всегда нужно одинаковое количество операций.Было бы более интересно, если бы вы позволили добавлять несколько книг одновременно.

Дисплей

Таким образом, дисплей распечатывает все книги в стопке.Если вы увеличиваете количество книг, число операций также возникает.Теперь вопрос в том, каким образом?В этом случае удвоение количества книг удваивает количество инструкций.Это линейный рост, поэтому класс сложности равен O (n) .

. Это может быть полезно для просмотра количества циклов.Один цикл по размеру проблемы часто означает O (n).Если у вас есть два вложенных цикла (по размеру задачи), у вас часто есть O (n²) и так далее.

На ваш вопрос, что такое бесконечный цикл в вашей основной функции, хорошо, это зависит от того, что вы определяете как размер вашей проблемы, я не знаю, имеет ли смысл здесь измерять его.

Если вы определите общее количество действий пользователя как размер проблемы, это усложняется.Если мы выпустим часть отображения и разрешим только добавление и удаление, то это O (n), потому что все будет константой (поскольку add и delete являются O (1), а другие вещи являются независимыми инструкциями, такими как cout), и они происходят вцикл, основанный на размере задачи n (количество действий пользователя).Если принять во внимание отображение, это не так просто, потому что отображение имеет сложность O (m) (m = количество книг), и это сильно зависит от фактического пользовательского ввода, который был дан ранее.Я не знаю, какова будет сложность там.

...