Zdravím, potřebovala bych poradit, jak vypočítat složitost daného algoritmu. Vím že na to musím přes součet geometrické posloupnosti, ale nějak se nemůžu chytnout. Například tenhle příklad:
Napište kolikrát se provede funkce foo(); (přesně, následně co nejlepší aproximací a následně jako funkci n.
for(i=0; i<2*n; i+=2)
for(j=i; j<n; j++)
foo();
Zjistila jsem si že první for cyklus mi proběhne nkrát. Druhý v prvním kroce proběhne nkrát, a v dalších krocích n-2krát, n-4krát... a vlastně n-2nkrát? Je to tak?
Teď jsem to chtěla dosadit do vzorce Sn=a1+an/2 * n ale nevychází mi to vůbec podle výsledků, kde je tedy chyba?
Za každou radu moc děkuju :)
Offline