Diskuze: Časová složitost algoritmů
Člen
Zobrazeno 7 zpráv z 7.
nevím proč, ale nešlo mi přiložit pseudokod, takže to celé hodím do code
Selection-Sort(A[0:n - 1])
1 for j <- 0 to n - 2
2 do iMin <- j
3 for i <- j + 1 to n - 1
4 do if A[i ] < A[iMin] then iMin <- i
5 t <- A[j ]; A[j ] <- A[iMin]; A[iMin] <- t
následně si rozepíšu jednotlivé operace a vypočítám viz. obrázek
nevím jestli to dělá správně, popřípadě bych prosil o vysvětlení
Ona je to docela věda, ale většinou dostaneš pár cyklů, co něco dělají s nějakou kolekcí.Stačí se podívat kolikrát ty cykly jedou v nejhorším případě. V tomto případě máš cyklus co projede n prvků a v něm další cyklus co projede n prvků. Dohromady tedy n2. Něco jsem o tom tady na devbooku napsal, četl jsi to?
U třídícího algoritmu tě zajímá počet porovnání prvků a počet prohození prvků.
n-1 + n-2 + n-3 + ... + 1 = n*(n-1)/2 = (n*n - n)/2 krátn-1 krátTakže celkový počet operací je (n2 - n)/2 + n - 1
Po úpravě n2 / 2 + n / 2 - 1
Asymptotická složitost O(n2 / 2 + n / 2 - 1) = O(n2)
Pokud potřebuješ spočítat ještě amortizovanou složitost, pak si pro pole o velikosti n vezmi všechny permutace a pro jednotlivé případy spočítej počet porovnání a z nich aritmetický průměr. V tomhle případě je ale jasné, že to bude opět O( n2 )
Dneska jsem se teda díval na ostatní algority(Insert, Bubble, Merge, Heap, Qiuck - sort) a jestli jsem to správně pochopil, tak selection, bubble a insert se odůvodní/vypočítá tímto způsobem
U třídícího algoritmu tě zajímá počet porovnání prvků a počet prohození prvků.
- porovnávání děláš na řádce 4 a ta se provede kolikrát pro pole A o velikosti n
n-1 + n-2 + n-3 + ... + 1 = n*(n-1)/2 = (n*n - n)/2 krát
- prohazování děláš na řádce 5 a ta se provede kolikrát pro pole A o velikosti n
n-1 krát
Takže celkový počet operací je (n2 - n)/2 + n - 1
Po úpravě n2 / 2 + n / 2 - 1
Asymptotická složitost O(n2 / 2 + n / 2 - 1) = O(n2)
Pokud potřebuješ spočítat ještě amortizovanou složitost, pak si pro pole o velikosti n vezmi všechny permutace a pro jednotlivé případy spočítej počet porovnání a z nich aritmetický průměr. V tomhle případě je ale jasné, že to bude opět O( n2 )ostatní jsou "vysvětlené ve skriptech"
Zobrazeno 7 zpráv z 7.