Új algoritmusok c. könyv. Ezt a néhány dolgot jól értem?

Ezt a futásidő - bonyolultság - futási sebesség dolgot úgy lehet megérteni, ha közben milliós, milliárdos nagyságrendekben gondolkodsz.

10, 20, 100 szám rendezésénél teljesen mindegy hogy mit használsz, a futásidő is pár milliszekundum (kivéve talán a Bogosort).

Viszont ha sok számod van, akkor nagyságrendben a c-hez képest az n-es tag kerül előtérbe. Tehát hiába nagyobb a log2(n) bonyolultságú algoritmusod futásideje az n^2-esnél mondjuk 100-ig, ha utánna kegyetlenül megugrik és évekig rendezné azt a sorozatot, amit a log2(n) bonyolultságú csak egy napig.

Ennek az egésznek úgy van értelme, hogy nagyságrendileg felméred mennyi adatod lehet, milyen gyors a vas, mennyi a memória (az algoritmusok memóriaigénye is ilyen változó, 1-től n-ig) és ezek alapján választasz megfelelőt a sok közül.

És programozz ilyeneket sokat, nézegesd a futásidőt, mérj, kísérletezz.

Gondolkodtató példákat találsz a projecteuler.com-on ilyen témában.

"6. kérdés. Mit értünk bonyolultság alatt?"

A számítógéptudomány ezt a problémát úgy közelíti meg,

hogy egy feladat elvégzéséhez szükséges számítástechnikai erőforrások (idő, tár, prog-

ram, kommunikáció) mennyiségével méri a feladat bonyolultságát, számszerű összefüggéseket ad meg rá.

"Ha beszúró rendezésnek n^2 a bonyolultsága, logikusnak tűnik hogy az összefésülőnek n*log2(n) és éppen érteném, de írtad hogy az összefésülőnek log2(n), szval nem értem. "

Nem jól írta, log2(n) nem is lehet semmilyen általános rendező algoritmus futási ideje.

"7. kérdés. A rendezéseknél meg van adva hogy mennyi a futásideje, de később ha az algoritmust implementálják bejön egy másik futásidő és a kettő összezavar."

Algoritmus futási ideje:El kell rugaszkodni a fizikai idő fogalmától. A terminálsásig szükséges elemi műveletek száma. Minden műveletnél meg kéne határozni hogy mennyi elemi műveletből áll és melyik műveletet hányszor hajtotta végre. (Ha fizikai időt elemeznénk akkor még bejönne egy tényező főleg ha nem valós idejű multikasztos rendszeren futtatjuk, ami azért van mert más algoritmusok is futnak a miénken kívül, akkor függne az operációs rendszertől, milyen prioritással fut, a hardvertől (mennyi processzor van, mennyi mag, melyik milyen gyors). Csak valószínűségeket számíthatnánk. Ezért jön ki sokszor más idő ha sokszor lefuttatjuk és lemérjük ugyanarra az inputra, még ha csak milisec különbségek lesznek.) Fizikai időt azon kívül hogy rendkívül elbonyolítja azért sem számolunk mert nem szolgál új információval az algoritmussal kapcsolatban. A c1,c2 stb. konstansokat elegendő 1-nek venni, így is elegendően pontosak vagyunk, nem érdekel minket hogy 10x vagy 100x több vagy kevesebb a futási idő mert konstansszor több vagy kevesebb. Mindegy hogy pentium1-es gépen futtatom vagy intel core i7-es gépen, lehet hogy 50x lassabban fut a pentium1-es gépen, ez a gép jellemzője nem az algoritmusé. Az is mindegy hogy egy értékadó művelet hány elemi műveletből áll, a lényeg hogy konstans számú, mert algoritmusokat elemzünk nem fizikai gépeket. Erre vannak az aszimptotikus jelölések. c1*n*log2(n), nem szokták írni hogy hányas alapú logaritmus, az is mindegy igazából mert a különböző alapú logaritmusok konstans szorzóban térnek el. Erre írják hogy O(n*log(n)).

Van még kérdés?

Megpróbálom akkor sorban, remélem tudok segíteni:)

1. futási idő ~ elemi műveletek száma

Egyenesen arányos vele, mértékegységük egészen más.

(hasonló: t = s / v)

A számítási sebesség mértékegysége: [link]

2. c1 az egy elem rendezéséhez szükséges elemi lépések számát jelöli. Korrekt.

3. Az implementáció a konkrét megvalósítása az algoritmusnak, programkóddal. c1 az implementációt jellemzi.

4. A konkrét implementáció is mindig más idő alatt fut, más gépen meg főleg. Viszont az elemi műveletek száma (c1) nem változik.

5. A megoldásod helyes, csak ez lényegtelen. Ránézésre látszik, hogy az n^2 hamar otthagyja az n*log2(n)-t, ahol fontos a futási idő(sok) ott sosem lesz jobb az n^2.

6. Hülyeséget írtam. A bonyolultság a domináns tag, ami nagy számoknál "átveszi a vezetést".

O( 1500 + 2*n + n^2 ) = O(n^2)

O( 3 + n^12 + n! ) = O(n!)

[link]

7-8. Igen, remélem fejlebb megválaszoltam.

Remélem nem írtam nagyon hülyeségeket.

"Ez baromság vagy ígyvan?"

Általában közelítőleg úgy van, a korábbi válaszomba benne van a válasz hogy miért nem. Valós idejű rendszeren lehet pontosan úgy mint ahogy írtad.

"Tehát futási idő = elemi műveletek száma, és a futási idő itt nem a fizikai időt jelenti. Ez korrekt?"

Első megközelítésben igen, de algoritmus futási ideje szempontjából bonyolultsági kategóriát szoktak érteni.

[link]

Amit a kolléga írt FLOPS-ot az csak az egyik mértékegysége, van a MIPS is, de itt nem ezekről van szó.

"Ha az algoritmust implementálják oda jön be egy futási idő, de az t(n) osztva sebesség, korrekt?"

A valóság általában ennél bonyolultabb, speciális valós idejű rendszereknél lehet pont így.

"Tehát egy probléma bonyolultsága = a megadott képletek "c" szorzótényező nélkül, korrekt? "

Nem (elég pongyolán fogalmaztál), ez a bonyolultságának egy jellemzője. Algoritmusok bonyolultságával a bonyolultságelmélet foglalkozik.

""1. futási idő ~ elemi műveletek száma

Egyenesen arányos vele"

Ez arra az esetre vonatkozik ha az algoritmust implementálták ugye? Mert ott van hogy sebesség = elemi műveletek / futási idő, viszont elemi algoritmus szintjén aztmondtuk hogy a futási idő jelenti az elemi műveletek számát a terminálásig. "

Kb igen. (Egyértelmű.)