Algoritmická zložitosť
Z Psychostudia
Hlavná stránka / Umelá inteligencia / Vybrané kapitoly z umelej inteligencie
To, že je niečo riešiteľné neznamená to, že to nutne dokážeme riešiť v konečnom čase a na konečnej pamäti.
Inými slovami je dôležité analyzovať algoritmy riešenia minimálne z dvoch hľadísk:
- Časovej zložitosti T(n)- počet krokov ktoré musí daný program s danými údajmi vykonať.
- Priestorovej zložitosti S(n)- miesto, ktoré k tomu potrebuje.
obyčajne sa uvádza ako funkcia nejakého parametra vstupných údajov. rozlišuje sa pre prípad:
- - najhorší
- - priemerný
- - najlepší
Pre hodnotenie sa využívajú najmä asymptotické vlastnosti miery:
- Hovoríme že miera je asymptotický polynomiálna keď existuje taký polynóm p(n), že T(n) < p(n)pre skoro všetky n (t.j. s výnimkou konečného počtu prípadov).
- Hovoríme že miera je asymptotický exponenciálna keď existuje dve také exponenciálne funkcie e1(n) a e2(n), že e1(n)< T(n)<e2(n) pre skoro všetky n (t.j. s výnimkou konečného počtu prípadov).
Prijíma sa názor, že úloha je principiálne neriešiteľná pomocou počítača ak ju nemôžeme riešiť rýchlejšie než v asymptoticky exponenciálnom čase.
[upraviť]
Zdroje
- Csontó, J., Sabol, T.: Umelá Inteligencia. (skriptum) Technická Univerzita Košice, 1991;ISBN 80-7099-104-6
- P. Sinčák, G. Andrejková: Neurónové siete Inžiniersky prístup. TU Košice, Elfa-Press, 1996, ISBN 80-88786-38-X.
