4 ms·
This is misleading twice over. First, as a3_nm notes, this proof depends on unproven conjectures, and so this isn't proven yet. Secondly, it is possible to do
by larsga 11y ago
This is misleading twice over. First, as a3_nm notes, this proof depends on unproven conjectures, and so this isn't proven yet.
Secondly, it is possible to do better than the Wagner-Fischer algorithm in certain cases. I figured this out myself and was about to write a paper on it when I realized that other researchers had beat me to it by a couple of decades.
If the two strings are equal you can establish that the edit distance is 0 in linear time, obviously. If you consider how the algorithm fills out the square down the diagonal you'll see that if there's only a one-letter difference you only actually need to fill out small parts of the grid around that difference.
This is generalizable, so the complexity actually depends on the distance between the strings.
- podgib 11y agoIn practice, yes, the computation time required to compute edit distance will depend on the actual data. Similarly, 'sorting' a list that is already sorted can be done in linear time, and near-sorted lists can be sorted much faster than a randomly ordered list. This is certainly useful in practice, but it doesn't affect whether the worst- or average-case complexity is quadratic. I'd like to see a quadratic (or exponential etc) time problem that couldn't be solved faster in many cases.