Vlákno názorů k článku Komiks: programátor lážo-plážo od BLEK. - Ja programuji i ve spanku. Ve spanku me...

Ja programuji i ve spanku. Ve spanku me napadaji ty nejlepsi algoritmy. Dokonce jsem ve spanku vymyslel radici algoritmus s linearni slozitosti. Bohuzel ho chapu ale jen ja, protoze mam poruchu osobnosti.

jo keď som programoval aj ja tak aj mňa v spánku napadla brutálna optimalizácia kódu ale mal som 13 a len som začínal v BASIC-u :)
Teraz už väčšinou neprogramujem(radšej) lebo som lenivý a bojím sa poruchy osobnosti...

To je fuk, hlavne jestli funguje. Proste ho napis. Nebo je ta porucha osobnosti ve skutecnosti porucha chapani slozitosti algoritmu? ;-)

Tohle psal falešný BLEK.

Né, tohle také psal falešný BLEK.

Nee tohle a to před tím psal taky falesnej BLEK. Ale asi už začínám mít taky poruchu osobnosti, když takhle kravím.

a tohle pro zmenu pise falsnej BLIK.

Pravý BLEK. netřídí, protože má poruchu osobnosti

A když jsou všechna čísla stejná, je to v O(1) no-need-sort. :-D

>Zial je dokazane, ze vseobecny sort nemoze byt lepsi ako O(N log N).

Ne, dolni hranici algoritmu je O(N), protoze vzdy musite prinejmensim zjistit, jestli jsou cisla opravdu serazena. Algoritmus s O(N) existuje, ja osobne znam dokonce dva - bohuzel jsou oba dva prakticky nerealizovatelne, protoze zatimco ten prvni je zalozne na kvanove mechanice, many-world intetrpretaci principu neurcitosti spojene s eliminaci nevhodnych skutecnosti (viz http://en.wikipedia.org/wiki/Bogosort#Quantum_Bogosort ), druhy zase potrebuje stroj casu schopny poslat informaci do minulosti (viz http://en.wikipedia.org/wiki/Time_loop_logic , jen by se misto delitele prvocila generovala permutace a misto testu delenim by se pouzila kontorla serazenosti).

U implementace pomoci specialniho hardware se da dokonce dostat k O(log N), ale vzhledem k jeji hardwarove slozitostoti je prakticka pouzitelnost mala, viz http://en.wikipedia.org/wiki/Sorting_network .

Máte v tom docela solidní guláš, mícháte složitost v modelech Turingova stroje, PRAMu s ruznými mírně řečeno nestandardními modely. ("dolni hranici algoritmu je O(N)" vs. "se da dokonce dostat k O(log N)" - jak to vysvětlíte)

Dokázáno je, že sekvenční program, který se z každého stavu může dostat jen do konečně mnoha dalších, a třídí posloupnost čísel, má složitost Omega(n log n), kde n je délka posloupnosti. To není nijak v rozporu s tím, že je to Omega(n), jak tvrdíte.

Jinak vytvořit třídící síť s O(n log n) komparátory a O(log n) hloubkou mi nepřijde až tak "fundamental problem" jak píšou na Wikipedii, a i použít by se to dalo (nad hardwarovou FFT se taky nikdo nepozastavuje).

To znám, jednou se mě zdálo o jedné krásné datové struktuře a zrovna v nejlepším se jsem musel probudit.

Me se na dnesek zdalo ze jsem jel na skejtu z kopce a najednou jsem tam hodil krasny slajd a byl to zuzo pocit. Jen ten slajd ve skutecnosti neumim. Nevite jak se to dela? Mam teorii ze clovek musi pouzit poradne rotaci tela, az pujdu skejtoat, musim to vyzkouset.

Slajdy jsou na prd, lepší je flipovat, onehda jsem si u toho pěkně zrakvil nohu, měsíc jsem pořádně nechodil, to byl mazec