Milyen algoritmussal lehetne a leghatékonyabban megoldani a következő problémát?

Átgondoltam : "Vagy ( abs(x) , abs(y) , abs(z) ) számhármas lexikografikus rendezési relációja szerint?"

Ez nem is helyes, mert nemnegatív számot kell kapni mindig. E helyett pl lehetne az hogy mondjuk lexikografikusan rendezve az 500 db számhármas. A listába hogy hanyadik elemű egy számot rendelni hozzá és két elem távolsága a listában hanyadik elem ezen indexek különbsége.

"megtalálni azt a kombinációját (ismétléssel és anélkül is)"

Vagyis gondolom úgy érted, hogy egy elemet többször is ki lehet választani , másik esetben pedig nem.

Ha nem ismétléses akkor kiválasztható e 2x ha 2x ugyanolyan értékű elem létezik a listába?

"A jelenlegi megközelítés itt az, hogy random kiválasztok egyet az 500-ból, ismételgetem addig amíg még nem lépi át a paraméterben megadott limitet,"[...]

A brute force-nál gyorsabb a backtrack algoritmus,azaz visszalépéses keresés. Így egy csomó keresési teret kihagysz amit a brute force bejárna feleslegesen.

Az egyetemista hozzászólónk gondolom jobban tudja, én már sokat felejtettem, de van olyan is hogy A* algortimus.

Van a szimulált hűtés nevű algoritmus, ahol kezdetben nagy kitérések vannak az optimumhoz képest az egyes iterációs lépéseknél. Majd egyre tovább futtatva egyre kisebb eltérések lesznek. Az elnevezés analóg a fizikában a részecskék "nyüzsgésével", ha forró az anyag jobban "nyüzögnek" a részecskék, ha hül akkor egyre kevesebb lesz a "nyüzgés".

"Utána néztem a backtracknek, nagyon izgalmasan hangzik. Így ránézésre nem mondanám az ordóját hatékonyabbnak mint a brute forcenak, de nálam lehet a gond :)"

Így ordóba nem lehet megmondani,de a legrosszabb esetbe meg lehet határozni az meg pont annyi mint brute force-ba. Konkrét esettől függ, hogy a keresési térből mennyit vág le. Ezzel szemben az N királynő problémája esetében jobban meghatározható a backtrack és a brute force különbsége.

Ugyanakkor az ordó sem minden esetben irányadó. Például a gyorsrendezés futási időben legjobb és átlagos esetében O(n*log(n)) , legrosszabb esetben O(n^2). Az összefésülő rendezés pedig legjobb, átlagos és legrosszabb esetben is O(n*log(n)). Mégis általában a gyorsrendezés a leggyorsabb az összehasonlító rendezések közül.

Egy hack hogy ne lehessen konkrét legrosszabb esetet mondani a gyorsrendezésre, rendezés előtt random összekeverni az elemeket, ez O(n) idejű, így O(n)+O(n*log(n)) = O(n*log(n)) .

"bocs a kicsit offtopic-ért, de mi a különbség az ordó és a legrosszabb eset között?"

Legrosszabb idő bonyolultság, legjobb idő bonyolultság és átlagos idő bonyolultság esetében írtam ordóban.

A gyorsrendezés példánál maradva, tudjuk hogy az egy önrekurzív algoritmus. A rekurzív híváskor ketté vágja a tömböt, bal és jobb oldalra. Az algoritmus rekurzívan kap egy pivot index-et, melynél kisebb elemek balra, a többi elem jobb oldalra kerül. Majd ezen bal és jobb oldal tömbre is kiszámolja a pivot index-eket, majd rekurzívan meghívja önmagát. Egésszen addig olyan hívási mélységig tart a hívási lánc míg 3-nál kevesebb elem van.

Átlagos esetben O(n*log(n)) idő bonyolultságú, de gondoljuk végig hogy legrosszabb esetben ez nem így lesz. Legrosszabb esetben a bal-jobb kettévágáskor és minden rekurzív híváskor az egyik oldalt mindig csak egyel csökken, azaz a bal, jobb oldal közül mindig egy elemű lesz az egyik. Ekkor kaptál egy négyzetes idejű rendezést O(n^2).

Egyébként hogy precízebb legyek a gyorsrendezés átlagos esetben theta n*log(n) azaz θ(n*log(n)). Viszont amire igaz hogy θ(n*log(n)) arra igaz, hogy O(n*log(n)). Fordítva nem minden esetben igaz.

[link]

[link]

[link]