Výpočet časové složitosti
Dobrý den,
prosím potřeboval bych pomoc, dostali jsme zadaný příklad na složitost a já si s ním vůbec nevím rady.
1. Nechť t-čas vykonání metody vykonej(). Odvoďte čas výpočtu programu T v závislosti na n a t v nejhorším případě. Dosaďte t=2 a vyjádřete čas T jako funkci n. Dokažte asymptotickou složitost O(n2) pro T(n)
Pomůcka: Napište definice, zvolte n0 a najděte hodnoty konstant c1 a c2.
for (int i =n-1; i>=1; i--)
for (int j=0; j<=i-1; j++)
if(a[j] > a[j+1]){
vykonej();
}
Nějak jsi neuvedl, co je a[].
Tam je uvedené že ostatní časy zanedbáme.Jinak a[] uvedeno není.
Dobře. A v čem máš tedy problém?
Mno já si napíšu definici ale už nevím jak zvolit n0 a celkově nevím jak se to dělá. Pročetl jsem už několik stránek ale pořád to nechápu.
Stačí si logicky odůvodnit kolikrát to celé proběhne v závislosti na n.
takže ten vnější proběhne (n-1) (n-2) ..... (n-n)? a vnitřní (n-2) (n-3) .... (n-(n+1))? a jak to bude u toho if?
Protože a[] neznáme, tak musíme předpokládat, že to proběhne pokaždé.
Takze ten if proběhne n-krát? A ty for cykli by taky meli tedy probehnout n-krat ne?
Vnější proběhne (n-1)krát, vnitřní 0 až (n-1)krát. If vždy. Takže složitost n^2.
a ten vypočet je (n-1)*0+(n-1)*n?
(0 + n-1)/2 * (n-1)
Ale konstanty můžeme ignorovat. Takže n*n.
a kde se vzalo to /2?
Průměr z 0 až n-1.
jop. mám tu ještě jeden příklad.
for(int i =0; i<=2*n-1; i++){
vykonej1();
}
for (int i=0; i<=n-1; i++){
for (int j=0; j<=i; j++){
vykonej2();
}
}
Takže ten první proběhne (n-1)-krát a u druhýho vnější (n-1)-krát a ten vnitřní 0 až (n-1)-krát.
takže výpočet je : (n-1)+(n-1)*(0+(n-1))/2=(n^2-1)/2 takže složitost je zase n^2?
Tak výsledek by tu měl být n^2+3n ale to mi rozhodně nevyšlo nejak furt nevím jak poznat kolikrát to proběhne
Neni to nahodou asymproticky n^2 - stejne se to +3n zanedbá, tak proc se s tim handrkovat?
for(int i =0; i<=2*n-1; i++){
vykonej1();
}
i tohodle? Nna2 prece nemuze byt vysledek ani omylem - je to 2naN - nekoliv čtvercově ale exponenciálně složité.
První proběhne 2n-krát.
Druhý n * (1 + n) = n^2 + n.
n^2 + n + 2n = n^2 + 3n
děkuji. akorát jak to že první proběhne 2n-krát?
i<=2*n-1
aha moc děkuji
v tom pripade se omlouvam, muj post je spatne ;) bral jsem to jako mocninu a ono jen to jen nasobeni ;)
ono je prece fuk kolikrat to probehne, protoze IF muze rozhodnout ANO NE pokud ANO v 70% pripadu, pak se to vykona 0,7x vnitřní LOOP, jenže 0,7 je konstanta a na konstanty se v asymptotice mrdá
Z asypmtotického pohledu neni třeba předpokládat nic - včetně toho kdyby to pokaždé bylo nesplnitelné - ten IF stejně proběhne vnitřní LOOPkrát.
ono takhle já pak mám dokázat tu asymptotickou složitost takže v podstatě je jedno jestl ido definice dosazuji n^2 nebo n^2+3n?
U velkých n je nějakých 3n oproti n^2 zanedbatelné.