Otázka k popisu

[misko256]

Dobrý deň

Chcel by som sa opýtať, pokiaľ v riešení používam quicksort, musím ho v popise vysvetľovať, prípadne zdôvodňovať jeho časovú zložitosť? Môjmu popisu by to strojnásobilo dĺžku .

Ďakujem

[USAmec]

Malo by stacit zhrnut niekolkymi vetami, ako funguje a aka je jeho ocakavana casova zlozitost.

[misko256]

Ďakujem veľmi pekne za rýchlu odpoveď.

[Baklažán]

To akože fakt treba popisovať aj také algoritmy? Podľa mňa je to dosť veľká strata času pre opravovateľa a riešiteľovi to nič nedá, keďže popis mu stačí copy-paste-núť z hocijakého zdroja.

[USAmec]

No ono treba nejak rozlisit medzi:
a) clovekom co napise sort(pole.begin(), pole.end()) a nechape co sa deje vo vnutri
clovekom co napise to iste, ale chape co sa deje vo vnutri a keby bolo treba, tak to dokaze aj implementovat

A ten popis podla mna nie je az tak dlhy, teda ja kebyze mam niekde popisovat triedenie, tak pisem asi nieco taketo:
"Pole utriedim v case O(N log N). Keby som to mal pisat, tak napisem merge sort, ktory rozdeli pole na dve rovnake casti, tie rekurzivne utriedi a potom ich spoji v case O(N)."

Samozrejme druha vec je trocha sudnosti. V nejakom 8mom priklade uz triedenie popisovat skor netreba, ale v takej 1-5 sa to urcite hodi aspon na 2 vety.

[Koniiiik]

(27.10.2011 20:07:22)Baklažán Napísal:  To akože fakt treba popisovať aj také algoritmy? Podľa mňa je to dosť veľká strata času pre opravovateľa a riešiteľovi to nič nedá, keďže popis mu stačí copy-paste-núť z hocijakého zdroja.

Lebo inak by svet vyzeral ako user-contributed komentáre k manuálom PHP? d-: (Napríklad, keď chceš zistiť počet dní medzi dvoma konkrétnymi dátumami, vedel si, že veľmi efektívnym spôsobom je postupne pripočítavať po jednom dni k tomu prvému, až kým nepresiahneš ten druhý? (-: (-: )

Seriously. Riešiteľovi to niečo dá, pokiaľ predtým nevedel, ako sort funguje. Pokiaľ vedel, nedá to až takú námahu stručne zhrnúť.

Povedal by som, že za copy-paste v riešení veľa bodov nebude, pokiaľ na to opravovateľ príde. Také niečo o úrovni znalostí riešiteľa nehovorí naozaj skoro vôbec nič.

[Xellos]

take porovnanie vyhod a nevyhod oboch pristupov:

copy-paste:
vyhody - mozem ziskat viac bodov za menej casu, co mi snad da ucast na sustredeni a dajaku knizku ak skoncim dost dobre
nevyhody - neda mi to nic viac, t.j. na sutaziach ako OI mi to nepomoze vobec, ani za uspechy v KSP sa nic velke ziskat neda; mozno tie body ani neziskam pretoze copy-pastnuty popis bude zly resp. opravovatel na to pride

popis z vlastnej hlavy (pripadne taky ze si pozriem algoritmus na internete a snazim sa pochopit o com je, potom sa snazim to nejako interpretovat):
vyhody - viac viem, nabuduce si to mozno uz budem pametat
nevyhody - sanca ze som to zle pochopil a mam za to menej bodov, viac casu na to treba

Ako mozeme vidiet, v oboch pripadoch to bodovo pomoct moze a nemusi, na druhej strane sa v 2. pripade naucim viac. Nie je to lepsie?

[mišof]

Technically, keď niekto vie nájsť dostatočne dobrý popis naozaj efektívneho triedenia a pastnúť ho do popisu, tak už podľa mňa je na dostatočnej úrovni aby tomu aspoň zhruba aj rozumel

[Koniiiik]

(28.10.2011 12:33:37)Xellos.myopenid.com/ Napísal:  nevyhody - sanca ze som to zle pochopil a mam za to menej bodov, viac casu na to treba

Ešte si zabudol spomenúť, že v tomto prípade ti vie vedúci vysvetliť, kde presne sa v tvojich myšlienkových postupoch udiala chyba a v konečnom dôsledku ti vie pomôcť lepšie to pochopiť. (-;

[Baklažán]

Ja som myslel skôr možnosť, že algoritmu rozumiem, ale som lenivý vymýšľať dôkladný (taký, z ktorého by sa dal jednoducho napísať rovnako efektívny algoritmus) popis (alebo mám deadline o 2 hodiny a 4 nevyriešené príklady) - a vtedy je to podľa mňa strata času aj pre riešiteľa aj pre opravovateľa.

Druhá vec je popis na dva riadky - súhlasím s tým, že to až tak veľa času nezaberie.

[Koniiiik]

(29.10.2011 11:17:06)Baklažán Napísal:  som lenivý
[...]
(alebo mám deadline o 2 hodiny a 4 nevyriešené príklady)

Solving KSP

You're doing it wrong.

(One of these days si musím zmeniť avatar na trollface. Alebo aspoň tomu hojdaciemu koníkovi dopaintbrushovať namiesto hlavy. d-: )