Big O 无缓冲区链表去重速度
我指的方法是双指针技术。其中第一个指针是一个简单的迭代器，第二个指针仅遍历相对于第一个指针的所有先前值。
这样，与针对每个节点与每个其他节点进行比较相比，完成的工作量更少。最终结果是 O(n^2)。
我的问题是双指针方法的速度是多少？为什么？
The approach I'm referring to is the dual-pointer technique. Where the first pointer is a straightforward iterator and the second pointer goes through only all previous values relative to the first pointer.
That way, less work is done than if, for each node, we compared against every other node. Which would end up being O(n^2).
My question is what is the speed of the dual-pointer method and why?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
因此，如果列表中有
N个元素，则对元素i进行重复数据删除将需要i比较（有i其后面的值）。因此，我们可以将比较的总数设置为sum[i = 0 to N] i。此总和的计算结果为N(N+1)/2，当N > 时，该总和严格小于.N^2。 1.编辑：
要解决求和问题，您可以这样处理。
1 + 2 + 3 + 4 + ... + (n-2) + (n-1) + n从这里，您可以匹配两侧的数字。 可以将其变为通过将开头的
1与匹配，2 + 3 + ... + (n-1) + (n+1)n 位于末尾。对2和(n-1)执行相同的操作。3 + ... + (n-1+2) + (n+1)简化为3 + ... + (n+1) + (n+1)< /code>您可以重复此操作
n/2次，因为您每次都匹配两个数字。这将导致术语(n+1)出现n/2次。将它们相乘并化简，我们得到(n+1)(n/2)或n(n+1)/2。请参阅此处了解更多说明。
另外，这表明该求和仍然具有
n^2 的大θ值。So if you have
Nelements in the list, doing your de-duping on elementiwill requireicomparisons (there areivalues behind it). So, we can set up the total number of comparisons assum[i = 0 to N] i. This summation evaluates toN(N+1)/2, which is strictly less thanN^2forN > 1.Edit:
To solve the summation, you can approach it like this.
1 + 2 + 3 + 4 + ... + (n-2) + (n-1) + nFrom here, you can match up numbers from opposite sides. This can then become2 + 3 + ... + (n-1) + (n+1)by matching up the1at the start with thenat the end. Do the same with2and(n-1).3 + ... + (n-1+2) + (n+1)simplify to become3 + ... + (n+1) + (n+1)You can repeat this
n/2times, since you are matching up two number each time. This will leave us withn/2occurances of the term(n+1). Multiplying those and simplifying, we get(n+1)(n/2)orn(n+1)/2.See here for more description.
Also, this suggests this summation still has a big-theta of
n^2.