Autor Wątek: [Algorytm] Złożoność czasowa  (Przeczytany 653 razy)

Offline mis02

  • Użytkownik

# Maj 18, 2011, 22:32:22
Witam,
próbuję policzyć złożoność czasową dwóch algorytmów. Książka "Algorytmy i struktury danych" niewiele mi w tym pomaga.
Gdyby ktoś mógł pokazać mi jak to liczyć, byłbym bardzo wdzięczny.

Pierwszy kod to wstawianie do listy posortowanych elementów:
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);
}

Drugi:
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++;
}
}
troszkę bardziej zamieszany. Nie ma co tłumaczyć, oba wycinałem z większego projektu.

Nie wiem nawet jak to ugryźć :/



// EDIT:
Rozwiązane na innym forum, wyszło O(n^2) :p
« Ostatnia zmiana: Maj 18, 2011, 23:35:37 wysłana przez mis02 »

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Offline counterClockWise

  • Użytkownik

# Maj 18, 2011, 23:57:29
Ale przecież List jest pusta i pętla iterująca po niej nigdy się nie wywoła.
Np. w drugim przypadku n razy wczytasz t i nic poza tym...

Offline lukaszw

  • Użytkownik

# Maj 19, 2011, 18:08:12
Ale przecież List jest pusta i pętla iterująca po niej nigdy się nie wywoła.
Z tego, co widzę w kodzie pierwszym - n razy jest wstawiany nowy element do listy. Znalezienie miejsca na nowy element w liście wymaga pesymistycznie tyle kroków ile jest elementów w liście. W i-tym kroku lista zawiera i elementów. Z tego wynika, że złożoność algorytmu wynosi O(n^2).
Drugi kod nie dodaje nic do listy - jest chyba niezbyt poprawny.