[Algorytm] Złożoność czasowa

mis02
Użytkownik
Użytkownik
Posty: 30
Rejestracja: 15 gru 2009, o 17:19
Płeć: Mężczyzna
Lokalizacja: ///
Podziękował: 6 razy
Pomógł: 3 razy

[Algorytm] Złożoność czasowa

Post autor: mis02 »

Witam,
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);
}
Drugi:

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

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.
Crizz
Użytkownik
Użytkownik
Posty: 4094
Rejestracja: 10 lut 2008, o 15:31
Płeć: Mężczyzna
Lokalizacja: Łódź
Podziękował: 12 razy
Pomógł: 805 razy

[Algorytm] Złożoność czasowa

Post autor: Crizz »

Złożoność naprawdę wystarczy oszacować, rzadko przydaje się dokładna postać funkcji kosztu. Często można to zrobić na logikę, biorąc pod uwagę najgorszy przypadek.

Weźmy pierwszy fragment kodu. Mamy pętlę, która zawsze wykona się n razy. Zatem instrukcje std::cin >>t oraz List.insert (it, t) Wykonają się również n razy. Instrukcja w pętli for wykona się (w najgorszym wypadku) zawsze tyle razy, ile jest dotychczas elementów w liście. Najpierw wykona się zero razy, potem raz, potem dwa razy itp. Możemy oszacować, że średnio wykona się ok. \(\displaystyle{ \frac{n}{2}}\) razy. Całkowita ilość instrukcji, które przypadają na pętlę for (już biorąc pod uwagę to, że jest ona wewnątrz while), wynosi zatem ok. \(\displaystyle{ \frac{n^2}{2}}\). Cała pętla while, w zależności od \(\displaystyle{ n}\) obejmie zatem \(\displaystyle{ An+Bn^2}\) instrukcji (\(\displaystyle{ A,B>0}\) będą pewnymi stałymi - \(\displaystyle{ An}\) bierze się z instrukcji std::cin >>t oraz List.insert (it, t), natomiast \(\displaystyle{ Bn^2}\) z pętli for).

Mamy funkcję kosztu postaci \(\displaystyle{ An+Bn^2}\). Istotniejszym składnikiem jest \(\displaystyle{ Bn^2}\) (funkcja kwadratowa \(\displaystyle{ Bn^2}\) przynajmniej od pewnego miejsca będzie zawsze rosła szybciej, niż funkcja liniowa \(\displaystyle{ An}\), niezależnie od tego, jakie będą wartości \(\displaystyle{ A,B}\)). Stąd złożonością tego algorytmu jest \(\displaystyle{ O(n^2)}\).

Jeśli korzystamy z funkcji bibliotecznych, to trzeba oczywiście dowiedzieć się, jaką złożoność mają one same. Możemy jednak podejrzewać, ze skoro już mamy iterator ustawiony na miejsce, w które chcemy wstawić nowy element (nie trzeba go szukać), to funkcja insert wykona się w stałym czasie.
mis02
Użytkownik
Użytkownik
Posty: 30
Rejestracja: 15 gru 2009, o 17:19
Płeć: Mężczyzna
Lokalizacja: ///
Podziękował: 6 razy
Pomógł: 3 razy

[Algorytm] Złożoność czasowa

Post autor: mis02 »

Dzięki wielkie za obszerne tłumaczenie

Z tego wynika że dla drugiego przypadku też będzie \(\displaystyle{ O(n^2)}\), tak?


EDIT:
I jeszcze jedno pytanie:
W pierwszym kodzie wstawiam tak elementy żeby lista była posortowana.
Równie dobrze mógłbym je powstawiać jeden za drugim, co dla n elementów da mi \(\displaystyle{ O(n)}\), a potem posortować przy użyciu std::list::sort() o złożoności \(\displaystyle{ O(n log n)}\).
Co mi wyjdzie w takim przypadku?

\(\displaystyle{ O(n) + O(n log n) = ?}\)

\(\displaystyle{ O(n log n)}\)? Bo zawsze będzie większe od \(\displaystyle{ O(n)}\)? Dobrze myślę?
Crizz
Użytkownik
Użytkownik
Posty: 4094
Rejestracja: 10 lut 2008, o 15:31
Płeć: Mężczyzna
Lokalizacja: Łódź
Podziękował: 12 razy
Pomógł: 805 razy

[Algorytm] Złożoność czasowa

Post autor: Crizz »

Odpowiedź na oba pytania jest twierdząca.
ODPOWIEDZ