performance - 无缓冲链表删除重复数据的大 O 速度

Question

我指的方法是双指针技术。其中第一个指针是一个简单的迭代器，第二个指针仅遍历与第一个指针相关的所有先前值。

这样，与对于每个节点，我们与其他所有节点进行比较的情况相比，完成的工作更少。最终将是 O(n^2)。

我的问题是双指针方法的速度是多少，为什么？

Answer 1

因此，如果N列表中有元素，则对元素进行重复数据删除i将需要i比较（后面有i值）。因此，我们可以将比较总数设置为sum[i = 0 to N] i。此总和计算结果为N(N+1)/2，严格小于N^2for N > 1。

编辑：要解决总和，您可以这样处理。

1 + 2 + 3 + 4 + ... + (n-2) + (n-1) + n 从这里，您可以匹配对面的数字。这可以成为

2 + 3 + ... + (n-1) + (n+1)通过匹配1开头和n结尾的。2对和做同样的事情(n-1)。

3 + ... + (n-1+2) + (n+1)简化成为

3 + ... + (n+1) + (n+1)

您可以重复此n/2次数，因为您每次都匹配两个数字。这将给我们留下n/2术语的出现(n+1)。将它们相乘并化简，我们得到(n+1)(n/2)or n(n+1)/2。

有关更多说明，请参见此处。

此外，这表明该总和仍然具有n^2.