Smith-Waterman-Algorithmus
Smith-Waterman-Algorithmus

== Effizienz ==
Die Laufzeitkomplexität des Smith-Waterman-Algorithmus ist in  und der Speicherbedarf in . Dies kann man einfach aus den Matrix-Rekurrenzen ableiten.
Weil man die Score-Matrix zeilen- bzw. spaltenweise berechnen kann, braucht man jeweils nur die aktuelle und die letzte Zeile bzw. Spalte zu speichern, wenn man nur den Score und nicht das Alignment berechnen möchte. In  dem Fall liegt der Speicherbedarf in  bzw. .
In linearem Speicherbedarf kann man auch das lokale Alignment mit Hilfe der Programmiermethode Divide-and-Conquer berechnen. Siehe Hirschberg-Algorithmus.