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?