• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Złożoność obliczeniowa algorytmu

VPS Starter Arubacloud
0 głosów
523 wizyt
pytanie zadane 1 listopada 2020 w Algorytmy przez niezalogowany

Witam, mam do obliczenia złożoność obliczeniową następującego algorytmu:

#include <iostream>
#include "List.h"

void menu(void);

int main(void)
{
    List *lista = list_create();

    int wybor;
    menu();
    while (std::cin >> wybor)
    {
        switch (wybor)
        {
            case 1:
            {
                for (int i = 1; i <= 100; i++)
                    list_push_front(lista, i);

                break;
            }

            case 2:
            {
                if (!list_empty(lista))
                {
                    std::cout << "\nWARTOSCI\n";
                    for (Node *i = lista->head; i != NULL; i = i->next)
                        std::cout << i->data << " ";

                    std::cout.put('\n');
                }
                else
                    std::cout << "\nWypelnij liste!\n";

                break;
            }

            case 3:
            {
                if (!list_empty(lista))
                {
                    double suma = 0.0;

                    for (Node *i = lista->head; i != NULL; i = i->next)
                        suma += i->data;

                    std::cout << "\nSrednia z listy to " << suma / lista->size << std::endl;
                }
                else
                    std::cout << "\nWypelnij liste!\n";

                break;
            }
            
            case 4:
            {
                if (!list_empty(lista))
                {
                    for (Node *i = lista->head; i != NULL; i = i->next)
                    {
                        /*
                            Jeśli element jest nieparzysty, usunie go.
                            Następnie przypisze do i element poprzedni
                            do usuniętego lub następny do usuniętego,
                            jeżeli jest różny od NULL.
                        */
                        if (i->data % 2 == 1)
                            i = list_pop(lista, i);
                    }
                }
                else
                    std::cout << "\nWypelnij liste!\n";

                break;
            }

            default: 
            {
                std::cout << "Niepoprawna opcja!\n";
                break;
            }
        }

        std::cout.put('\n');
        menu();
    }

    list_free(&lista);

    return 0;
}

void menu(void)
{
    std::cout << "1. Wypelnij liste wartosciami 1...100\n";
    std::cout << "2. Wyswietl liste\n";
    std::cout << "3. Oblicz srednia i ja wyswietl\n";
    std::cout << "4. Usun wartosci nieparzyste\n";
    std::cout << "Twoj wybor (wartosc nieliczbowa konczy): ";
}

Według mnie będzie to stała klasa złożoności obliczeniowej O(1), ponieważ pierwsza opcja wykona się zawsze 100 razy, druga też 100 razy, trzecia również, czwarta 51 razy ze względu na moją implementacje funkcji list_pop. Czy dobrze rozumuje?

komentarz 1 listopada 2020 przez tkz Nałogowiec (42,000 p.)
Nie zapomniałeś o jakiś plikach? Na przykład .c i .h, które są odpowiedzialne za implementacje listy.
komentarz 1 listopada 2020 przez niezalogowany
W tym przypadku one nie mają znaczenia, powiedzmy że to są operacje podstawowe.
komentarz 1 listopada 2020 przez tkz Nałogowiec (42,000 p.)
Jakim cudem 4 case wykona się 51 razy, skoro iterujesz po całej liście?
Skoro wszystko masz ustawione na sztywno, to nie możesz oczekiwać innej złożoności jak stała, o ile wszystko inne również jest o stałej złożoności. Jaki jest sens określenia jakiejkolwiek złożoności w tym przypadku?

1 odpowiedź

0 głosów
odpowiedź 1 listopada 2020 przez SimiVoid Pasjonat (19,790 p.)
Wg mnie złożoność tego algorytmu będzie wynosić O(n), ponieważ to, że coś się w tym przypadku wykonuje określoną ilość razy nie znaczy, że złożoność konkretnego algorytmu będzie liniowa - O(1). Jak pojawiają się pętle to trzeba patrzeć na ich ilość, czy się nie zagnieżdżają w sobie, a jak pojawia się rekurencja to w jaki sposób się wywołuje.

Podobne pytania

0 głosów
1 odpowiedź 209 wizyt
pytanie zadane 25 kwietnia 2020 w C i C++ przez Tacoo Nowicjusz (150 p.)
0 głosów
2 odpowiedzi 367 wizyt
pytanie zadane 5 grudnia 2019 w Algorytmy przez progNewbie Obywatel (1,130 p.)
0 głosów
1 odpowiedź 222 wizyt

92,455 zapytań

141,263 odpowiedzi

319,099 komentarzy

61,854 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...