A Wiki meghatározza a polinomiális időt ugarként:
Az algoritmus állítólag polinomi időtartamú, ha futási idejét felső részén egy polinom kifejezés határolja az algoritmus bemenetének mérete, azaz $ T (n) = O (n ^ k) $ valamilyen állandó $ k $ esetén
I értsd meg, hogy általában véve a polinomiális idő és a exponenciális idő az, hogy az exponenciális függvény szignifikánsan gyorsabban növekszik, mint bármely polinom függvény, aszimptotikusan ( hivatkozás ).
Megpróbálom megérteni a magot A definíciója: exponenciális idő .
- Milyen elemek miatt fog egy algoritmus futtatni a Exponenciális idő ?
- Milyen változást kell végrehajtanom a polinom kifejezésben Exponenciális idő ? ( it al az algoritmus definíciójára utalok az elején kérdés)
Megjegyzések
- 1. Tegyen exponenciálisan sok mindent. 2. Használja a polinomot egy bázis hatványaként > 1.
- Nem értem ' nem értem a másodpercét kérdés. A polinomok polinomok; az exponenciálisok exponenciálisak. Az a kérdés, hogy mit kell változtatnia ahhoz, hogy egy polinomból exponenciálissá váljon, olyan, mintha azt kérdezné, hogy mit kell változtatnia ahhoz, hogy a logaritmusból koszinusz legyen.
- @DavidRicherby Lesznek-e exponenciális időfüggvények, ha P = NP? Hogyan definiálhat egy exponenciális időfüggvényt a polinomiális kifejezés szempontjából?
- Exponenciális függvények továbbra is léteznek, ha P = NP. Valószínűleg még mindig vannak olyan problémák, amelyek ' akkor is exponenciális időt vesznek igénybe, ha P = NP, bár egyik sem merül fel azonnal. Az exponenciális függvény meghatározható polinomként, de ennek a végtelen hosszúnak kell lennie – érdemes felkutatnia a Taylor-bővítéseket, ha ' érdekli.
- @ymbirtt Az időhierarchia tétel legegyszerűbb változata is azt mondja, hogy egyetlen EXPTIME-teljes problémára sem létezik polinom-idő algoritmus. Ez ' feltétel nélküli eredmény: nem ' nem attól a feltételezéstől függ, hogy P $ \ neq $ NP.
Válasz
-
Erre nincs könnyű válasz, bár vannak jelek, amelyekre figyelni kell . Például egy halmaz minden lehetséges részhalmazának vizsgálata exponenciális – tehát ha egész számom lenne $ \ {x_1, …, x_n \} $, és ezek összes részhalmazát szerettem volna ellenőrizni, hogy összeadódnak-e $ 0 $ -ig, pontosan $ 2 ^ n $ -halmazokat kell figyelembe vennem, ami ezt a módszert exponenciális idővé teszi. Több különböző csapda képes az algoritmust exponenciális idővé tenni, azonban tág kategóriák keresése helyett elemezzen algoritmusokat eseti alapon.
-
Ha egy algoritmus $ n ^ 2 $ lépést tesz szükségessé, akkor az polinom. Ha $ 2 ^ n $ lépést hajt végre, akkor exponenciális. A különbség a $ n $ pozíciója. Ha valami $ O (n ^ m) $ = $ n > 1 $, $ m > 0 $, akkor “s” polinom $ n $ -ban fix $ m $ -hoz, de exponenciális $ m $ -hoz fix $ n $ -hoz.
Megjegyzések
- Óvatos. A $ n ^ m $ függvény nem ' t polinom a $ n $ értékben, hacsak a $ m $ nem állandó. És ha $ m $ konstans, nincs értelme ' annak a kijelentése, hogy a függvény ebben az állandóban exponenciális.
- Igen, te ' igaza van. Én ' ezt tisztázom.
Válasz
Gyakran kap egy exponenciális időtartamú nyers erő algoritmust, amikor egy problémát megfontol, és felsorolja annak teljes keresési területét. Jellemzően részhalmazproblémákra gondol (SAT-ban az változók igazra vannak állítva), permutációs problémák (a TSP-ben minden turné a városok permutációja) és partíciós problémák (gráf színezésében megpróbál a csúcsokat színosztályokba osztva). Vagy vegye fontolóra a párosítást: $ n! $ Permutációja van $ n $ egész számnak. Végezzen el minden permutációt és ellenőrizze, hogy rendezve vannak-e. Buta (és lassú), de működik.
Megjegyzések
- Bár vegye figyelembe, hogy $ O (n!) $ Még rosszabb, mint $ O ( k ^ n) $. Ha ' még mindig megpróbálja megismerni az idő bonyolultságát, ez hasznos dolog lehet, hogy bebizonyítsa magának.