Content deleted Content added
Undid revision 965275578 by 119.18.2.71 (talk) |
→"Partial match" table (also known as "failure function"): Added complexity analysis considering also the inner loop |
||
Line 426:
'''let''' T[pos] ← cnd (only need when all word occurrences searched)
===Efficiency of the table-building algorithm===
The time (and thus space) complexity of the table algorithm is <math>O(k)</math>, where <math>k</math> is the length of <code>W</code>.
* The outer loop: <code>pos</code> is initialized to 1, the loop condition is <code>pos < k</code>, and <code>pos</code> is increased by 1 in every iteration of the loop. Thus the loop will take <math>k - 1</math> iterations.
* The inner loop: <code>T[cnd]</code> is always less than <code>cnd</code>, so <code>cnd</code> gets decreased by at least 1 in each loop iteration. <code>cnd</code> is initialized to <code>0</code> and gets increased by at most 1 in each outer loop iteration. This means that the inner loop can execute at most as many times in total, as the outer loop has executed – each decrease of <code>cnd</code> by 1 in the inner loop needs to have a corresponding increase by 1 in the outer loop. Since the inner loop takes <math>k - 1</math> iterations, the inner loop can take no more than <math>k - 1</math> iterations in total.
Combined, the outer and inner loops take at most <math>2k-2</math> iterations. This corresponds to <math>O(k)</math> time complexity using the [[Big O notation]].
==Efficiency of the KMP algorithm==
|