Hogy lehet kiszámolni egy kód idő, és tér komplexitását?

Nem írom le ide, mert ez egy komplett szakág, algoritmuselmélet a neve.

Van sokféle képlet, meg matek mögötte...

Ami neked lényeg, egy statikus kód analízis tool kéne, van olyan, amelyik meg tudja mondani.

A legegyszerűbben, a gyenguszok, matek undoritiszben szenvedők számára úgy, hogy:

- veszel egy doksit, ami tartalmazza a target processzor utasításainak listáját és a műveletek elvégzéséhez szükséges ciklusidőket. Ebből készítesz egy .csv fájlt.

- a forráskódból a fordítóval .asm kimenetet generáltatsz.

- írsz egy python/basic/c/pascal/java/whatever_you_want parsert, ami az .asm fájlból, a .csv segítségével kiszámolja és szummázza a ciklusidőket.

Ez lesz a time, azaz, az időigény.

- Ugyanezt a műveletet elvégezteted a felhasznált változók tipusainak tárigényével és az előfordulási gyakoriságukkal.

Na, ez utóbbi lesz a space, azaz, a tárigény.

Ha viszont következtetni is akarsz, na, azt már nem úszod meg matek nélkül.

O(1): állandó időkomplexitás, az algoritmus futási ideje nem változik a bemenet méretével.

O(log n): logaritmikus időkomplexitás, az algoritmus futási ideje logaritmikusan nő a bemenet méretével.

O(n): lineáris időkomplexitás, az algoritmus futási ideje lineárisan nő a bemenet méretével.

O(n^2): négyzetes időkomplexitás, az algoritmus futási ideje négyszereződik a bemenet méretének megduplázódásával.

O(2^n): exponenciális időkomplexitás, az algoritmus futási ideje exponenciálisan nő a bemenet méretével.

Tuladonképpen csak végig kell gondolni, hogy mit is csinál az az algoritmus.

De mivel nem sok esély van rá, hogy valami eredeti algoritmust fogsz kitalálni, ezért elég az alapalgoritmusok komplexitását figyelmbe venni és ha ezeket kombinálod, akkor megkapod a saját algoritmusod komplexitását.

Az alapalgoritmusok komplexitását meg megtalálod itt:

[link]

Ha mégis valami bonyolultabb esettel találkoznál, akkor bele kell magad ásnod a témába:

[link]