Matematické Fórum

↑ VojtechSejkora: Stačí sa len trochu pošťúrať... http://ksp.mff.cuni.cz/zaciname/faq.html
Tak sa prečo neopýtaš na to čomu nerozumieš vo všeobecnosti a potom sa to nepokúsiš aplikovať sám na svoj problém?

↑ VojtechSejkora:

Vůbec jsem nepochopil zadání...
Máš zadanou nějakou časovou složitost a co s ní máš dělat?

↑ VojtechSejkora:

Aha, tak zadání už chápu, ale ta tvoje časová složitost je nějaká divoká :)
Dej sem tu funkci a stručnej popis jak funguje a co to dělá...

↑ VojtechSejkora:

Složitost není zrovna moje silná stránka, ale snad to co napíšu nebude mimo :)
Máš tam jeden vnější for cyklus, kterej jede přes všechny prvky pole -1. Uvnitř se něco dělá a pak tam je další for cyklus. To by svádělo napsat, že to bude kvadratická složitost, ale to podle mě není. Cílem není zjistit kolikrát přesně ten kterej cyklus pojede, ale jde o to zjistit jakej bude nejhorší případ.
Ten vnitřní for cyklus tě podle mě v tomhle případě vůbec nezajímá protože ten není závislej na počtu prvků na vstupu. Takže budu předpokládat, že pojede přes celej rozsah integeru. Tím pádem celej ten vnitřek má konstantní časovou složitost k. Výsledná složitost by pak byla (N-1)*k, takže celkově to je lineární složitost.

↑ VojtechSejkora:

Jak sem dopsal ten minulej příspěvek tak sem ještě psal pár takových teoretických poznámek...
Nejdřív sem to chtěl smazat, ale teď  to sem dám:

Jinak ještě bych k tomuhle chtěl napsat jednu věc.
K čemu je tohle všechno dobrý a co ti to řiká o tom algoritmu?
Obecně jde prostě o to aby algoritmus spadnul do co nejnižší třídy časový složitosti. Ideálně do konstantní, když to neklapne tak do lineární, nebo do logaritmický atd atd. Čím nižší třída časové složitosti, tím menší bude mít vliv zvyšující se počet na celkovou dobu běhu programu. Takže obecně kvadratická složitost je horší než logaritmická atd. Na první pohled jasná věc. Když se ale vrátím k tomu tvýmu algoritmu a to k bude počet sekund za který se zpracuje ta jedna iterace toho vnějšího for cyklu, tak klidně řeknu, že to bude třeba 1000s - což je dost dlouho. Teď když někdo napíše jinej algoritmus, který bude mít třeba kvadratickou složitost a ten vnitřek se bude zpracovávat jenom 1s, tak z hlediska časový složitosti bude tenhle algoritmus horší.
Řekněme, že třeba pro 10 prvků bude ten tvůj algoritmus počítat 10*1000s a ten druhý 10^2*1s. Jak ale poroste počet prvků, doba běhu toho druhýho algoritmu bude narůstat daleko víc než u toho prvního...
Když si třeba nakreslíš do jednoho grafu, grafy funkcí 100000*N a 0,001*N^2, tak uvidíš, že pro dostatečně velké N bude mít ten druhý vyšší funkční hodnoty.
Co sem tím vším chtěl říct?
1) To že máš svůj algoritmus ve "správný" časový složitosti neříká nic o tom, jestli je optimální
2) Různě když třeba koukneš po netu, tak se dočteš, že tenhle algoritmus má kvadratickou složitost (n^2), jinej má složitost n*log (n) atd atd. To ale neznamená, že se nějaká iterace provede přesně n^2 -krát!!! To pouze znamená, že ta kvadratická složitost je jakoby dominující. Ve skutečnosti se nějakej ten cyklus může provést třeba n^2 + 24n - (3n+k) + atd atd


K tomu tvýmu poslednímu příspěvku...
Nevím jestli to úplně chápeš. Co myslíš, tím, že se pro 4 prvky O=2? Dvě čeho??? Ten tvůj algoritmus bude trvat dvě vteřiny nebo se tam něco provede dvakrát?
Jinak tím k myslím samozřejmě konstantu. V nejhorším případě bude provedení toho vnitřku toho vnějšího for cyklu trvat k vteřin.

↑ VojtechSejkora:

Podle mě ti utíká několik zásadních věcí...
1) Ten graf nahoře, to je co? Nemáš tam popsaný osy, to je to nejdůležitější co tam musí být. Bez toho je to úplně bezcenný... Hádám, že na ose X máš počet prvků a na ose Y počet iterací, ale iterací čeho??? Počet iterací vnitřního for cyklu?
2) Z toho co píšeš v poslednim postu mám pocit, že se snažíš počítat kolik iterací bude mít ten vnitřní for cyklus v každé té iteraci toho vnějšího for cyklu... Proč??? Je ten vnitřní for cyklus závislej na počtu prvků na vstupu? Podle toho algoritmu co si uved, není. Ten vnitřní for cyklus je závislej na nějakých hodnotách minK a maxK, což rozhodně není počet prvků na vstupu, ale jsou to čísla, který si nějak vypočítal z hodnot prvků toho hlavního pole. Ty čísla jsou typu integer - tedy 32b. Já teda předpokládám, že v nejhorším případě pojede ten vnitřní for cyklus vždycky 2^32 krát. Ten vnitřní for cyklus bude tedy trvat v nejhorším případě vždycky konstantní čas.
Jinak řečeno, ten vnitřní for cyklus se nikdy neprovede víckrát než 2^32 krát. Tedy doba provádění toho vnitřního for cyklu nikdy nepřekročí nějaký konstantní čas. To, že postupně narůstá počet iterací vůbec nic neznamená protože ten nárůst se časem zastaví. Tohle je klíčový si uvědomit protože bez toho se nehneš dál.

Přijde mi, že sis udělal graf jak ti postupně narůstá počet iterací toho vnitřního for cyklu. Teď citace z toho tvýho posledního postu:

...který mi spočítal pro dost čísel kolikrát že se to provede a vyšla mi kvadratická

Co to je pro dost čísel??? Podle toho grafu je u tebe "dost" něco kolem 30000. Tímhle způsobem to ale nemůžeš dělat. Dost může být v některých případech třeba miliarda nebo sto miliard atd atd. "Dost" se případ od případu liší... Kdybys pokračoval v navyšování počtu prvků tak bys viděl, že se ten graf nezvedá už kvadraticky, ale lineárně.

Aby bylo jasný jak to myslim tak tady ještě obrázek


Doporučuju si udělat ještě jinej graf...
Vem si nějakej počet prvků a pak pro každý i (což je iterační proměnná toho vnějšího for cyklu) si zjisti kolikrát se proved ten vnitřní for cyklus. Na osu x si dej i a na osu y si dej kolikrát se proved ten vnitřní for cyklus. Zjistíš, že od určitýho okamžiku (ať bude i velký jakkoli) se ti už nebude zvyšovat hodnota na ose y. Rozhodně nikdy nepřeleze hodnotu 2^32.