[C++] Złożoność obliczeniowa i czasowa

[mzetka3]

Witam,
Czy może ktoś wytłumaczyć dlaczego w tej procedurze:

Kod: Zaznacz cały

f(int a)
{
	odp=0;
		for(i=1; i<n; i++)
		{
			for(j=1; j< 2*i mod 100;j++)
			{
				for(k=0; k<n*n; k++)
				{
					odp++;
				}
			}
		}
}

Złożoność obliczeniowa wynosi: \(\displaystyle{ n^{2}}\)
Złożoność czasowa: \(\displaystyle{ 4^{r}}\)

A nie odpowiednio:
\(\displaystyle{ n^{4}}\)
I \(\displaystyle{ 16^{r}}\)
Z góry dziękuję za wytłumaczenie zadania!
Pozdrawiam

[JumpSmerf]

Złożoność obliczeniowa algorytmu jest tym samym, co złożoność czasowa - są to pojęcia używane zamiennie. Złożoność obliczeniowa nie może być inna niż czasowa.
Trudno mi na pierwszy rzut oka określić, czy na pewno złożoność tej procedury wynosi \(\displaystyle{ n^{2}}\), ponieważ nie wiem co tu się dzieje. Napisz cały program i co on robi.

[mzetka3]

To niestety jest cały program z przedmiotu elementy analizy algorytmów
W tym przypadku:
Złożoność obliczeniowa - O duże
Złożoność czasowa - teta

[JumpSmerf]

Złożoność obliczeniowa - O duże
Złożoność czasowa - teta

Nigdy nie słyszałem, żeby ktoś to tak nazywał.
Notacja O, to funkcja oznaczająca, że algorytm ma złożoność co najwyżej rzędu n (złożoność pesymistyczna), a theta, że dokładnie rzędu n.
Nie powiem ci dlaczego tak jest, ale myślę, że należy tu wykorzystać analizę kosztu zamortyzowanego (, szeroko opisane we "Wprowadzeniu do algorytmów"). Nie czytałem jeszcze o tym, to ci nie mogę powiedzieć, czy na pewno korzystając z tego dowiesz się dlaczego tak się dzieje, ale tak mi się wydaje.

[95Villain95]

Wybaczcie za odkopanie, ale ćwiczę sobie obliczanie złożoności czasowej algorytmów i w związku z tym,czy ktoś może potwierdzić, że złożoność tego algorytmu to złożoność kwadratowa? Wydaje mi się, że może się to przydać również innym. Wychodzi mi coś takiego \(\displaystyle{ t_{1} + t_{2} \cdot (n-1)+ t_{3} \cdot n^{2}+ t_{4} \cdot n+ t_{5}}\) Z góry dzięki za pomoc.

[93Michu93]

To będzie coś takiego
\(\displaystyle{ \sum_{i=1}^{n} \sum_{j=1}^{2i mod 100} \sum_{k=0}^{n^2} 1 = \sum_{i=1}^{n} \sum_{j=1}^{2i mod 100} n^{2} = \sum_{i=1}^{n} n^{2} \sum_{j=1}^{2i mod 100}1}\)
Tutaj nie jestem pewny co z tym modulo zrobić ale to chyba będzie liniowo, a pierwsza suma O(\(\displaystyle{ n^{3}}\)) więc na pewno złożoność będzie wyższa od kwadratowej, moim zdaniem O(\(\displaystyle{ n^{4}}\)).