napisałem sobie dwa prościutkie fragmenty kodu, teraz potrzebuję policzyć ich złożoność czasową. Siedzę nad książką "Algorytmy i struktury danych" ale jakoś mi to nie idzie :/
Gdyby ktoś mógł pokazać mi jak to liczyć, byłbym bardzo wdzięczny.
Pierwszy kod to wstawianie do listy posortowanych elementów:
Kod: Zaznacz cały
std::list<int> List;
std::list<int>::iterator it;
int n, t;
std::cin >> n;
while(n--)
{
std::cin >> t;
for(it=List.begin(); it!=List.end(); it++) if(*it > t) break;
List.insert(it, t);
}
Kod: Zaznacz cały
std::list<int> List;
std::list<int>::iterator it;
int n, t, x;
std::cin >> n;
while(n--)
{
std::cin >> t;
x = 0;
for(it=List.begin(); it!=List.end(); it++)
{
if((*it) > t) break;
t -= (*it);
x++;
}
}
Nie wiem nawet która instrukcja głównie wpłynie na złożoność i od czego zaczynać to 'liczyć'. Pewnie wszystkie szczegóły implementacji STLowej listy są pomijalne.