dsg*_*dsg 6 language-agnostic algorithm complexity-theory
如线性时间多数算法的答案所示？,可以在线性时间和log(n)空间中计算元素数组的大部分.
结果表明,每个看过这种算法的人都认为这是一种很酷的技巧.但这个想法是否会推广到新算法？
似乎这个算法的隐藏力量在于保持一个扮演复杂角色的计数器 - 例如"(到目前为止多数元素的数量) - (到目前为止第二多数的计数)".是否存在基于相同想法的其他算法？
嗯,让我们首先开始理解为什么算法有效,以便"隔离"那里的想法.
算法的要点是,如果你有一个多数元素,那么你可以将它的每一个匹配与一个"另一个"元素匹配,然后你有一些"备用".
所以,我们只有一个计数器来计算我们的客座答案的"备用"次数.如果它达到0,那么从我们"选择""当前"元素作为客户主要元素到"当前"位置时,它不是子序列的多数元素.此外,由于我们的"guest"元素与所考虑的子序列中的所有其他元素匹配相匹配,因此在所考虑的子序列中没有主要元素.
现在,因为:
通过矛盾可以明显看出,如果存在一个主要元素,那么当计数器永远不会为零时,我们就会得到整个序列的后缀.
现在:在新的O(1)大小O(n)时间算法中可以利用的想法是什么？
对我来说,只要你需要计算P一系列元素的属性,就可以应用这种技术:
seq[n, m]可以seq[n, m+1]在O(1)时间内扩展到Q(seq[n, m+1])P(seq[n, m])可以在O(1)时间和空间中计算P(seq[n, j]),P(seq[j, m])如果Q(seq[n, j])成立则在我们的例子中,P我们的"选举"主要元素的"备用"事件Q是" P零".
如果你以这种方式看待事物,最长的共同子序列利用相同的想法(不知道它的"冷静因子";))