Tudtok olyan algoritmust mondani, aminek a futási idejét kiszámolni O (n! ) lenne?

Az utazó ügynök problémája.

Brute force-szal O(n!) lenne, bizonyos technikákkal kicsit javítható.

[link]

[link]

Nem értitek a kérdést.

Ne gyertek azzal, hogy há de úgy értettem, meg a kérdező biztos amúgy gondolta. Nem érdekel hogy gondolta, gondolat olvasási vizsgán azért nem mentem át sose mert nem tudtam előre mik a tételek.

Tudtok olyan algoritmust mondani, aminek a futási idejét kiszámolni O (n! ) lenne?

Vagyis : Tudtok olyan algoritmust mondani aminek előre nem tudjuk hogy mennyi a futási ideje, megbecsülni se tudjuk gyorsabban mint O(n!) időbe és pontosan ennyi időbe telik a meghatározása. Az hogy mennyi a futási ideje az más kérdés, vélhetően sokkal sokkal több.

Nem szokványos kérdés, az biztos. Csak a tisztánlátás kedvéért:

a) az algoritmus komplexitási osztályának meghatározása legyen O(n!) nehézségű, vagy

b) a takkra pontos futási idejének kiszámolása egy konkrét n hosszú bemenetre?

A b) esetre nem nehéz példát adni: bármilyen algoritmus, amelynek komplexitása O(n!), de nem fix lépésszámú n függvényében sem, így a futásidejének meghatározásához le kell futtatni. Példa: egy algoritmus, amely eldönti, hogy adott n különböző byte-nak létezik-e olyan permutációja, melynek SHA-512 hash-e 0. A "nem" esetekben n! lépés kell, az "igen" esetekben kevesebb, hiszen ahogy talál egy sikeres permutációt, végzett.

Ha az a) esetre gondoltál, akkor halvány gőzöm sincs, ahogy gondolom itt az oldalon senki másnak se. Már az se gyakori, hogy egy algoritmus komplexitási osztálya n-től függjön (pl. páros n-ekre O(n), páratlanokra O(exp(n)), bár gráfelméletből rémlenek ilyen dolgok). De hogy már pusztán ennek a meghatározása is O(n!) nehézségű legyen... hát, ezzel a kérdéssel szerintem a legedzettebb számításelmélet-professzorokat is megizzasztanád.