Złożoność obliczeniowa algorytmu

Question

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?

Comments

Nie zapomniałeś o jakiś plikach? Na przykład .c i .h, które są odpowiedzialne za implementacje listy.

---

W tym przypadku one nie mają znaczenia, powiedzmy że to są operacje podstawowe.

---

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?

Answer 1

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.