大O速度從鏈接列表中刪除重複項無緩衝區

Question

我指的是雙指針技術。第一個指針是一個簡單的迭代器，第二個指針只經歷所有與第一個指針相關的先前值。

通過這種方式，比對每個節點我們與其他每個節點進行比較所做的工作量少。這將最終成爲O（n^2）。

我的問題是雙指針方法的速度是什麼，爲什麼？

Answer 1

所以，如果你在列表N元素，元素i做你移除重複需要i比較（有i值後面）。因此，我們可以將比較的總數設置爲sum[i = 0 to N] i。該總和評估爲N(N+1)/2，嚴格小於N^2（對於N > 1）。

編輯： 要解決總和，你可以這樣來處理它。

1 + 2 + 3 + 4 + ... + (n-2) + (n-1) + n從這裏，你可以匹配來自對面的數字。這可以通過在末尾匹配1開始時的n而變成

2 + 3 + ... + (n-1) + (n+1)。與2和(n-1)一樣。

3 + ... + (n-1+2) + (n+1)簡化成爲

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

可以重複此n/2時間，因爲你是匹配了，每次有兩個號碼。這將使我們有n/2發生術語(n+1)。乘以這些和簡化，我們得到(n+1)(n/2)或n(n+1)/2。

查看here瞭解更多描述。

另外，this表明這個總和仍然有一個大的。