std :: set擦除複雜性異常？

我想弄清楚從std :: set中清除多個元素的複雜性。我正在使用this page作爲源。它聲稱使用迭代器擦除單個項目的複雜度爲O（1），但使用範圍形式擦除多個項目爲log（c.size（））+ std :: distance（first，last ）（即 - 集合的大小的日誌+刪除的元素的數量）。如果要擦除的元素的數量（n）遠遠小於集合（m）中的元素的數量，則這意味着循環遍歷待擦除的元素並擦除它們中的一個（O（n））比用一個呼叫擦除它們更快（O（log m），假設n爲< < m）。std :: set擦除複雜性異常？

很明顯，如果真的如此，第二種形式的內部實現只會執行上述循環。

這是該網站的錯誤？規格中的錯誤？我只是想念一些東西？

感謝， Shachar

來源

2014-03-03 Shachar Shemesh

_erasing使用範圍形式的多個項目是log（c.size（））+的std ::距離（第一，最後）（即 - 日誌中的集合的大小+元素的刪除數的）。 _ - 固定集合的大小與O（n）完全相同，其中n是被刪除的元素數量，這是您逐個刪除元素的數量。 – Cthulhu

這很有趣，我想你可以用兩種方法來測試它，看看差異。也許在每次擦除之後重置迭代器會有一些開銷（因爲我認爲這會使迭代器失效） –

@Cthulhu，只要在複雜度中使用加號，就會應用相同的邏輯。任何你假設不變（或甚至有界）的東西都會自動複雜爲O（1）。 –

看來問題是隱藏的（有點黃鼠狼）字「攤銷」的背後。單項擦除具有日誌（c.size（））的O複雜性，但是O（1）的分期複雜性。因此，在一個循環中執行多個單獨的擦除會花費日誌（c.size（））+擦除次數，這正是範圍形式的複雜性。

Shachar

來源

2014-03-03 10:44:24

「攤銷」不是一個黃鼠狼字。這是一個完善的計算機科學術語：http://en.wikipedia.org/wiki/Amortized_analysis。 –

好的，「黃鼠狼」有點苛刻。我認爲，放棄嚴格的上限聲明會引起混淆。如果你只提供操作的分期複雜性，你通常會剝奪程序員知道期望的能力。我同意只使用O複雜性可能同樣具有誤導性（如在這裏），但我認爲標準應該提到兩者。 –

std :: set擦除複雜性異常？

回答

相關問題