SearchInWindow算法的时间复杂度求解咨询

原算法代码 #

function SearchInWindow(p)
        for l ← 1 ... L do
                c_l ← CountOccurrences(p, l)
        end for
end function

复杂度推导 #

• 外层循环执行L次，每次对应片段长度l（从1到L）
• 每次调用的CountOccurrences(p, l)时间复杂度为O(l × W)，其中W是窗口长度
• 总时间复杂度为所有循环步骤的复杂度之和：将l从1到L的l×W累加，等价于W乘以1到L的和
• 1到L的和等于L*(L+1)/2，这个值就是组合数binom(L+1,2)
• 因此总时间复杂度为$O\left(W \times \binom{L+1}{2}\right)$，你的猜测完全正确。

内容的提问来源于stack exchange，提问作者DaBler