Prírodou inšpirované algoritmy

Efektívnosť

Najnáročnejšia časť KM modelu je relaxačný krok, keďže sa musia nájsť všetci susedia danej bunky. V najhoršom prípade bude zložitosť O(n2), kde n je počet buniek. Aby sa tomu predišlo, aplikujeme na doménu dynamickú štvorcovú mriežku. Lineárna veľkosť každého miesta v mriežke je rovná odpudivému polomeru. Potom nám stačí kontrolovať len 8 políčok mriežky v okolí danej bunky a ešte oblasť samotnej danej bunky. Každá oblasť mriežky má smerník na zoznam buniek, ktoré sa v nej nachádzajú. Keďže počet buniek rastie exponenciálne s časom, potrebujeme danú mriežku upravovať. S rastom domény bude rásť počet políčok mriežky, nie ich veľkosť.