Definice časové složitosti

[slowthinker]

Debata o tomto tématu začala mezi mnou a Matyášem Novákem ve vláknu Optimální algoritmus výpočtu, a aby se v jednom vlákně neprobírala dvě témata, odskočil jsem s ní sem.
(většina mých příspěvků a asi polovina Matyášových příspěvků ve vláknu "Optimální algoritmus výpočtu" je na toto téma)

Shrnutí dosavadní debaty:

Debata začala na tom, jaká je časová náročnost tohoto algoritmu (dále "nakupovací algoritmus"), já jej považuji za kvadratický, Matyáš Novák za pseudopolynomiální.

definice [1]
Matyáš Novák vychází z formální definice, a uvažuje asymptotickou časovou náročnost v závislosti na velikosti vstupu, za velikost vstupu striktně pokládá objem dat resp. bitovou délku vstupu.

definice [2]
Já říkám, že za velikost vstupu v této definici by se měla považovat "vhodná" charakteristika vstupu, v tomto konkrétním případě požadovaný počet kusů zboží (takováto definice by se ale špatně formalizovala - je těžké určit pro obecný algoritmus, která charakteristika je vhodná): potom vyjde složitost kvadratická.

definice [3]
Stejný výsledek dá "intuitivní definice" časové náročnosti podle struktury algoritmu: výše zmíněný algoritmus je tvořen dvěma dva vnořenými cykly od 1 do n, kde n je určeno vstupními hodnotami: je tedy kvadratický. (Tato intuitivní definice půjde asi těžko formalizovat, protože je založena na algoritmu probíhajícím v lidském mozku, a formalizace by znamenala určení tohoto algoritmu. Tento algoritmus by ale nedokázal určit svou vlastní složitost.)

Tyto rozdílné definice dávají také rozdílnou složitost algoritmu pro faktoriál (zde).

Edit: pojmenoval jsem definice a úlohu

[Reklama]

[slowthinker]

Odpověď na příspěvek Matyáše Nováka:

2) Neřekl jsem, že algoritmus, který by uměl pracovat s libovolně velkým n, je algoritmus složitější a pomalejší asymptoticky. Podstatné na tom mém sdělení je, že se jedná o jiný algoritmus: bude "nafouknutý" o tu "lineární" část, která bude zpracovávat neomezeně velká data.
1) + 4) Teorii algoritmů neumím, ale nemyslím si, že NP třídy a složitost musejí být definovány na Turingových strojích. Turingův stroj, počítač s libovolným přístupem, nebo reálný HW jsou výpočetně ekvivalentní, definice složitosti založené na těchto různých strojích budou také ekvivalentní.
Předpokládám, že i na reálném HW se časová složitost bude definovat podle počtu elementárních operací, nikoli podle doby běhu programu, takže věci jako branch prediction nás nezajímají.
3) Co má být jako omezeno při fixním zápisu vstupních dat? Počet slov na vstupu je vždy neomezený.

Chci tim říct, že bavit se o ASYMPTOTICKÉ složitosti, tedy vyšetřovat jaké je chování algoritmu při přibližování nějaké veličiny (ať již jde o délku vstupu nebo o cokoli jiného) limitně k NEKONEČNU, je u fixního vstupu blbost, protože fixní vstup se nikdy k nekonečnu blížit nebude, anžto má horní hranici.

Přibližování "nějaké veličiny"?? Tak moment, když jsem říkal, že tou veličinou má být vhodná charakteristika vstupu, oponoval jsi, že to musí být jedině bitová délka vstupu a nic jiného. A to z důvodu, že formální definice musí být jednoznačná (což považuji za důvod velmi rozumný).

Jestli tomu dobře rozumím, náš současný spor je založen na tomto: měříš velikost vstupu bitově a představuješ si, že velká čísla na vstupu mají větší objem než malá. Toto má samozřejmě vliv při výpočtu složitosti algoritmu.
Jenomže pokud chceš měřit délku vstupu, měl bys jí měřit počtem slov na vstupu. Pro abstraktní počítač bit vůbec neexistuje, a tím pádem nemůže existovat ani tvoje představa, že velká čísla na vstupu mají větší objem než malá.

[j.]

Jak zni otazka? Problem je, ze skustecne nemas teoreticke zazemi ani neovladas terminologii, a proto mas tendenci sklouzavat k naivnim definicim, coz prirozene vede k nepochopeni.

Porad se drzis toho, ze jedno cislo = jedno slovo na vstupu, a ze jedna aritmeticka operace nad cislem je provedena v konstatnim case. Diky masivni optimalizaci dnesnich stroju mas v tak v 80% pripadu pravdu, ale ne vzdy, a prave pri analyze chovani algoritmu nad obecnymi vstupy (kdyz cisla nejsou limitovana velikosti slova) se pouziva formalni definice, protoze abstrahuje od hardwarove optimizace, ktera se muze lisit masinu od masiny a vstupu od vstupu.

[Ghost]

Ja nevim co tady resite, vzdycky se uvadi asymptoticka slozitost (pripadne pametova).
1. trivialni (ovsem ne vzdy spravna) spodni mez se da odvodit od velikosti problemu - tj. serazeni N cisel by teoreticky mohlo byt provedeno v linearnim case - tedy N. Jenze skutecnost je, ze serazeni trva N.logN (je za tim pekny dukaz)

2. pocet trivialnich operaci (napr. porovnani, prirazeni atd.) vzdy pro nejhorsi mozne reseni. Nestaci, ze v 99% je nejaky algoritmus linearni a v 1% treba exponencialni. Slozitost bude exponencialni.

Co se tyka pseudopolynomialni a kvadraticka ? Toto trvzeni muze byt klidne pravdive.
Kvadraticka je polynomialni, na tom se shodnem asi vsichni. V pseudopolynomialni hraje roli jeste dalsi parametr, ktery se nesmi zanedbat!

[slowthinker]

Ghost: no to jsem si všiml, že nevíš co řešíme. Nechceš si debatu nejdřív přečíst, promyslet, a pak teprve reagovat?

[Reklama]

[slowthinker]

j.:
Otázek v té debatě zatím vyvstalo hodně, ale i v mých prvních dvou příspěvcích lze nalézt hodně otázek, opravdu je tu musím vypisovat?

• Je formální definice [1] (link v prvním příspěvku) nějak používána v praxi, nebo má význam jenom pro teoretické úvahy?
• Jak bys ohodnotil časovou složitost algoritmu pro výpočet faktoriálu, a pro "nakupovací algoritmus"?
• Má se pro stanovení časové složitosti uvažovat, že "velká čísla na vstupu mají větší objem než malá"? Příklad: výpočet faktoriálu, na vstupu jediné slovo. Mám velikost vstupu počítat tak, že 16 na vstupu má délku 4, a 32 délku 5?

Problem je, ze skustecne nemas teoreticke zazemi ani neovladas terminologii, a proto mas tendenci sklouzavat k naivnim definicim, coz prirozene vede k nepochopeni.

Já si naopak myslím, že k naivním definicím je potřebné sklouzávat (alespoň dokud nebudu vědět o jejich formálním ekvivalentu}, a vysvětlil jsem to už dříve v debatě. Zkusím argumenty shrnout znovu:
1. argument
Formální definice [1] (link v prvním příspěvku), podle které je algoritmus pro faktoriál exponenciální a "nakupovací algoritmus" lineární, nemá dle mého názoru praktický význam.
2. argument
Když argumentaci vezmu trochu obecněji: formální definice [1] nemá praktický význam, protože závisí na tom, jak je zakódovaný vstup. Matyáš Novák sice napsal, že by toto bylo možné vyřešit takto:

Proto nemá smysl se bavit u daného algoritmu o ničem jiném než o nejlepším možném algoritmu nad nejúspornějším možným vstupem.
A pokud vstup není efektivní, předřadit před samotný algoritmus nějaký filtr, který ho vyčistí

jenomže to už se nebude jednat o formální definici (alespoň já si nedovedu představit, jak formálně definovat "nejúspornější vstup").

A mimochodem, naivní definice [2] je používána i v dosti teoretických publikacích (Kučera: Kombinatorické algoritmy.)

Porad se drzis toho, ze jedno cislo = jedno slovo na vstupu, a ze jedna aritmeticka operace nad cislem je provedena v konstatnim case. Diky masivni optimalizaci dnesnich stroju mas v tak v 80% pripadu pravdu, ale ne vzdy, a prave pri analyze chovani algoritmu nad obecnymi vstupy (kdyz cisla nejsou limitovana velikosti slova) se pouziva formalni definice, protoze abstrahuje od hardwarove optimizace, ktera se muze lisit masinu od masiny a vstupu od vstupu.

O hardwarové optimizaci se snad nebavíme: všechny tři definice uvedené v 1. příspěvku abstrahují od hardwarove optimizace.

Číslem myslíš hodnotu vstupující do algoritmu? ( nechtěl bys zapracovat na terminologii?). V tom, že hodnoty nejsou limitovány velikostí slova, přece není problém, pokud je každý typ hodnoty reprezentován pevně daným počtem slov.
Změna nastává, pokud jsou hodnoty ukládány do neomezeného počtu slov: představ si algoritmus třídění, kde jednotlivé hodnoty určené ke setřídění nebudou reprezentovány K slovy (K pevné), ale libovolným počtem slov (vstupní hodnoty budou moci být neomezeně velké). Takový algoritmus se bude lišit od svého klasického protějšku, ale nevidím žádný důvod, proč bych měl na měření jeho složitosti potřebovat jinou definici. Je to algoritmus jako každý jiný.

[Ghost]

Ghost: no to jsem si všiml, že nevíš co řešíme. Nechceš si debatu nejdřív přečíst, promyslet, a pak teprve reagovat?

Prave, ze diskuzi sleduju uz docela dlouho.
A nevim co tady porad resis. V tematu se celkem orientuju a proto ti radim: Nstuduj si nejakou teorii. (sam pises, ze ji neznas)

Takto mi pripada, ze mlatis paty pres devaty a michas vsechno mozne dohromady.

PS. Smir se s tim, ze to je NP-uplny problem

[slowthinker]

ghost: ty vole, to snad ne 
  Doufám, že sis všiml, že celou dobu mluvím velmi spisovně, a že tvůj příspěvek mi patrně způsobil dosti silný otřes.
Tvůj předminulý příspěvek měl jistou informační hodnotu, i když obsahoval vesměs nesporné skutečnosti. Ovšem tvůj poslední příspěvek neměl vůbec žádnou informační hodnotu.
Debatu na dané téma myslím vedeme dost konkrétně, snaž se prosím také odpovídat konkrétně.

[Logik]

Teorii algoritmů neumím, ale nemyslím si, že NP třídy a složitost musejí být definovány na Turingových strojích.

Nemusí. Ale prostě je. Můžeš ji definovat jinak, ale pak se budeš bavit o voze, zatimco všichni ostatní o koze. Můžeš začít budovat novou teorii od základů, ale bojím se, že budeš v pozici strýce Františka ze Saturnina.
(Pokud už chceš budovat novou teorii, tak aspoň nepřetěžuj užívané termíny novými významy).

Neřekl jsem, že algoritmus, který by uměl pracovat s libovolně velkým n, je algoritmus složitější a pomalejší asymptoticky.

Takže jsou tydle možnosti.
a) Daný fakt je k posouzení asymptotické složitosti algoritmu irelevantní, nebo
a) Nebavíme se o asymptotické složitosti, jejíž definicí ses tady oháněl.

Navíc adaptace na dlouhá číslá nezmění ani stupeň polynomu absolutní složitosti (viz dál).

Co má být jako omezeno při fixním zápisu vstupních dat? Počet slov na vstupu je vždy neomezený.

To fakt nevíš??? Libovolná veličina zadaná pevnou délkou. Tzn. cena produktu, počet balení v produktu, chtěný počet produktů...

Tato intuitivní definice půjde asi těžko formalizovat.

Fór je v tom, že
a) formalizovat nepůjde
b) není schopna porovnávat různé algoritmy

A už vůbec nemluvím o tom, že algoritmy jsou na sebe převeditelné, a to co je v jednom vyjádřené počtem, je v druhém vyjádřené číslem. Např. teď mě napadá např. automatické dokazování, kdy se dá dokazované tvrzení reprezentovat jako seznam termů, logických spojek atd..., takže dle naivní definice je složitost daná počtem prvů ve výrazu, anebo jít podle důkazu gödelovy věty a tvrzení očíslovat - a najednou mám podle Tebe složitost vyjádrřit dle velikosti čísla.
Takže podle toho, jakou zvolím interpretaci vstupu, tak se mi mění složitost???

----

Teda abych byl formálně správnej, je pravda, že definice složitosti v NP úplnosti asymptotická není, pro složitost jsou definice dvě:

Asymptotická.
http://cs.wikipedia.org/wiki/Asymptotick%C3%A1_slo%C5%BEitost
Ta ale vyžaduje, aby veličina, podle které se složitost měří (tzn. se kterou rychlost algoritmu nejvíce klesala) rostla do nekonečna. Tzn. tuto definici nelze užít pro algoritmus, kde je chtěnej počet zadanej omezeným číslem.
Navíc i tato složitost se běžně definuje v závislosti na délce, byť se to někdy zjednodušuje na počet prvků na vstupu (neboť u většiny algoritmů nezávisí rychlost na velikosti zpracovávaných hodnot, ale na jejich počtu).

Absolutní:
http://wiki.matfyz.cz/wiki/St%C3%A1tnice_-_NP-%C3%BAplnost

Absoutní složitost je definovaná polynomem jako horní mez trvání algoritmu pro všechny vstupy dané délky v binárním kódování.
Tady fixní délka vstupu použít jde, ale jelikož délka toho argumentu bude vždy stejná, výsledná složitost na něm vůbec záviset nebude. Vzhledem k tomu, že jde o nejpodstatnější parametr (nejvíc ovlivňující rychlost výpočtu), považuji užívání tohoto formátu v této definici složitosti za metodologickou chybu.

Takže než bude debata pokračovat, tak by prosím bylo dobré definovat, o čem se bavíme.
Popř. jestli je debata právě o tom, kterou definici vlastně používat, tak odkazuju na svůj první odstavec - pokud chceme řešit, jestli je daný problém NP nebo ne, tak má imho jedině smysl definice, která se používá pro definici NP úplného problému.

[j.]

    * Je formální definice [1] (link v prvním příspěvku) nějak používána v praxi, nebo má význam jenom pro teoretické úvahy?
    * Jak bys ohodnotil časovou složitost algoritmu pro výpočet faktoriálu, a pro "nakupovací algoritmus"?
    * Má se pro stanovení časové složitosti uvažovat, že "velká čísla na vstupu mají větší objem než malá"? Příklad: výpočet faktoriálu, na vstupu jediné slovo. Mám velikost vstupu počítat tak, že 16 na vstupu má délku 4, a 32 délku 5?

1. Vyznam ma, i kdyz v trosicku jinych aplikacich (kryptografie, analyza opravdu velkych souboru dat, ...)
2. Faktorial - bez hlubsi analyzy predpokladam kubickou (nevim jestli neni nejaka optimalizace), co je to nakupovaci algoritmus?
3. Urcite, zapis vetsicho cisla v dvoukove soustave potrebuje vice mista. Ze granularita beznych systemu je 32/64 bit na tom nic nemeni. 

Formální definice [1] (link v prvním příspěvku), podle které je algoritmus pro faktoriál exponenciální a "nakupovací algoritmus" lineární, nemá dle mého názoru praktický význam.

Jisteze ma. Existuje spousta problemu, ktere se resi i pro vstupy vetsi nez jedno slovo. Napriklad cela moderni kryptografie a kryptoanalyza je zavisla na odhadu slozitosti podle delky klice, a tam uz opravdu velice zalezi jestli je delka klice 1024  nebo 2048b.

Když argumentaci vezmu trochu obecněji: formální definice [1] nemá praktický význam, protože závisí na tom, jak je zakódovaný vstup. Matyáš Novák sice napsal, že by toto bylo možné vyřešit takto:

Formalni definice ma vyznam tam, kde sa bavime o opravdu velkych vstupech - jako prave ta kryptografie a kryptoanalyza, priklady z teorie cisel, a pod.
Nema moc smysl se bavit o zpusobu kodovani vstupu, ten nema na tridu slozitosti (prakticky je jedno jestli se bavime o kubicke nebo bikvadraticke slozitosti, zajimave je, ze je to porad polynomialni). Kdyz se bavime o setrizeni n cisel na vstupu, bavime se o jinem algoritmu nez o setrizeni prvnich n cisel z posloupnosti 2^n. Pojdme se bavit o algoritmu tak, ze pri definici algoritmu definujeme i vstup ktery ocekava.

Kdyz mas ukol naplnit batoh se vstupem k_j1_j2_j3..., kde k, j1, j2 ... jsou dekadicke zapisy cisel, je to jiny algoritmus nez kdyz mas stejny ukol se vsupem, kde cisla jsou zapsana jako posloupnost carek hospodskym zpusobem, a uplne jiny algoritmus kdyz mas cisla zapsana v prirozenem jazyku. V praktickem zivote se vetsinou bavime o zapise cisla v n-arni soustave (n>=2), jednoduse proto, ze dostavame pouzitelnejsi vysledky nez kdybychom se bavili o jednickove soustave. To ovsem neznamena, ze vysledky s jednickovou soustavou musi byt nezajimave, z akademickeho hlediska. A algoritmus rozpoznavajici vstup v prirozenem jazyce by zajimavy urcite byl

O hardwarové optimizaci se snad nebavíme: všechny tři definice uvedené v 1. příspěvku abstrahují od hardwarove optimizace.

Ale ty ji porad implicitne predpokladas - HW optimalizace je i to, ze cislo (do urcite velikosti) ma konstatni velikost (co predpokladas) i to, ze aritmeticka operace nad dvema slovy je konstantni.

Číslem myslíš hodnotu vstupující do algoritmu?

Cislo je cislo, v ramci teorie cisel.

V tom, že hodnoty nejsou limitovány velikostí slova, přece není problém, pokud je každý typ hodnoty reprezentován pevně daným počtem slov.

To je jenom definice jestli je granularita 32, 64 nebo 1024 bitu - obecne ale musis pocitat s neomezene velkymi cisly na vstupu.

Změna nastává, pokud jsou hodnoty ukládány do neomezeného počtu slov: představ si algoritmus třídění, kde jednotlivé hodnoty určené ke setřídění nebudou reprezentovány K slovy (K pevné), ale libovolným počtem slov (vstupní hodnoty budou moci být neomezeně velké). Takový algoritmus se bude lišit od svého klasického protějšku, ale nevidím žádný důvod, proč bych měl na měření jeho složitosti potřebovat jinou definici. Je to algoritmus jako každý jiný.

No konecne na to zacinas prichazet Definice slozitosti se nemeni - v jednom pripade mas algoritmus na trideni slov do delky 32/64/XYZ bitu, ve druhem mas algoritmus na trideni cisel liovolne velikosti. Je jasne, ze ty algoritmy nejsou stejne a kazdy resi uplne jiny problem.

[slowthinker]

Já se vrátím.
(nemám teď moc času a Matyáš mě plně vytěžuje ve vlákně "Optimální algoritmus výpočtu".)

[Logik]

Jen dvě technické
1) imho u složitosti algoritmu má smysl se bavit o složitosti vzhledem k optimálnímu vstupu - tzn. zadaném v co nejúspornějším formátu. To sice zrovna příliš formalizovatelné asi není (různé komprese mohou zúspornit i na pohled nejúspornější formát), nicméně pro porovnávání náročnosti různých algoritmů je to myslím dostačující definice.
(Zformalizovat by to šlo např. tak, že pokud algoritmus A při svém běhu ignoruje hodnotu některých bitů na vstupu, pak existuje A', který příjmá stejný vstup s těmi bity vypuštěnými).

2) jedničková soustava je imho nesmysl, neboť algoritmus není schopen poznat konec vstupu. Pokud by detekoval konec vstupu podle konce vstupu, je "konec vstupu" v podstatě druhý symbol a jde tedy o soustavu dvojkovou.

[j.]

Ciste formalne: asymptoticka slozitost algoritmu zavisi od vstupu, ktery dany algoritmus ocekava. Pokud dany vstup neni "optimalni" (at uz si pod tim zadefinujeme cokoli) z hlediska reseni problemu, na slozitosti algoritmu to nic nemeni.

Spise se pojdme bavit o tom, do ktere slozitostni tridy patri ten-ktery problem. A pak uznas, ze problem "setrizeni n cisel zapsanych v binarni soustave oddelenymi jednou mezerou", problem "setrizeni n cisel, z nich kazde ma maximalni velikost 2^32, zapsanych v binarni soustave oddelenymi jednou mezerou" a problem "setrid n cisel zapsanych jako posloupnost jednicek oddelenych mezerou" nejsou stejne - kazdy z nich se zabyva necim jinym a nalezi do jine slozitostni tridy.

Mozna se ti naivne zda, ze ty problemy totozne jsou (aspon cisla 1 a 3), a snazis se najit nejakou definici ekvivalence, ktera by se s tim vyporadala (ve tvem pripade nalezeni redukce na problem s "optimalnim" vstupem), a zadefinovat slozitostni tridu na prislusnych tridach rozkladu. V principu mi to ale prijde ze to nikam nevede - kdyby ses to pokusil formalizovat, pravdepodobne to povede do neresitelnych problemu - tyto typy redukce nejsou nutne polynomialni, a povolenim nejakych ne-polynomialnich redukci skoncis na jedne tride rozkladu, zahrnujici jakykoli vycislitelny problem. Koneckoncu, spousta notoricky znamych redukci mezi NP-Complete se da preformulovat v prirozenem jazyce tak, aby zneli jako jeden problem s jinou definici vstupu.

A stavet podobnost na tom, ze se ti to intuitivne zda, resp. zadani v prirozenem jazyce zni podobne... - no, nic moc Drz se formalni definice.

(A kdyz uz formalne, predpokladam, ze vzhledem k existenci polynomialni redukce porad abstrahujeme od rozdilu mezi rozhodovacima problemama a problemama vypoctu funkce, resp. prislusnyma tridma slozitosti).

[nevim]

Panove, mohl bych vas o neco poprosit? Zajimalo by me vase vzdelani (kde, co a rocnik/dosazeny titul) . Od vsech...

[Logik]

nevim: Bc. mff informatika, studium hotový, píšu diplomku.

j: Jo, já s tebou souhlasim. Akorát si myslím, že by ty "problémový třídy definovat možná šly".

A stavet podobnost na tom, ze se ti to intuitivne zda, resp. zadani v prirozenem jazyce zni podobne... - no, nic moc

Souhlasím, pokud to nepůjde definovat formálněji, tak je to blbina :-).

Zkusil bych třeba:
Algoritmus A je podobný algoritmu B, pokud.
Existuje  funkce F: vstupy(B) -> vstupy(A) a G: výstupy(A) -> výstupy(B), které jsou
a) na
b) Pro každé b ze vstupů b platí B(b) = G(A(F(b)))
c) O složitost (tzn. se zanedbáním konstant) F a G je asymptoticky menší nebo rovna složitosti algoritmu B.

Máš pravdu, že tak by se dostali všechny NP do jedné třídy, to mě nenapadlo :-),
ono vlastně to říká, které algoritmy jsou schopny navzájem řešit své zadání.
Možná ještě zajímavější by bylo, kdyby G byla identita (tzn. vstup různý, ale požadavek na stejný výstup). Nicméně u rozhodovacích problémů se rozdíl stírá.

Největší problém, kterej v tomdle vidim je ten, že ta relace mezi algoritmama dosti pravděpodobně nebude tranzitivní (složením převodů už vzinkne tak složitej převod, že nevyhoví definici) a možná ani symetrická. Takže jde spíše o relaci, kdy ke aždému problému existuje množina "podobných problémů".

Nicméně i tak se mi zdá k něčemu - říká mi, v jakých formátech mohu příjmat vstup, abych pořád byl stejně rychle schopen vyřešit daný problém* a naopak jaké algoritmy mohu použít pro řešení daného problému (i když to je svým způsobem nadbytečná definice, protože G*A*F je taky algoritmus.

*) problém teď chápu jako ryze praktickou věc - prostě potřebuju něco vyřešit, co mám zadaný per huba. Tak najdu libovolný řešící algoritmus, k němu množinu podobných algoritmů a z ní si vyberu.

Ale stopro todle promyšlený nemam, neručim ,že tam neni někde díra :-)