什麼是通過NSSet和NSDictionary進行迭代的大O符號

我想知道什麼是通過NSSet進行迭代的大O符號。 NSArray的答案顯然是O（n） - 但NSSet的答案是什麼？另外 - 我假設相同的答案將適用於NSDictionary？什麼是通過NSSet和NSDictionary進行迭代的大O符號

來源

2014-10-04 YogevSitton

如果您關心性能，請確保使用「快速枚舉」或塊。不要使用常規的C'for'或'while'循環。 https://developer.apple.com/library/ios/documentation/Cocoa/Conceptual/Collections/Articles/Enumerators.html – 2014-10-05 09:34:50

這個問題更多的是好奇心話題，而不是我看到的實際問題 – YogevSitton 2014-10-05 12:04:27

。那麼，答案取決於集合中的內容。 NSSet不是一個簡單的類，如果實現有幾萬行代碼，我不會感到驚訝。對於初學者來說，甚至沒有一個名爲「NSSet」的真正課程。這只是一個名稱，用於連接所有進入集合的實際類，實際使用的類將根據集的內容和代碼訪問集的模式而改變。一般來說，一套5件商品與50件商品相比，會有很大不同的表現特徵。是的，它可以處理那麼多的數據。 – 2014-10-06 01:23:13

通過查看橋接Core Foundation等效項的標題中的註釋（因爲它們本質上使用相同的代碼），您可以瞭解Apple數據結構的計算複雜性。

有趣的是，CFArray時間複雜度是不實際上保證是O（N）：

計算複雜

爲所述陣列中的值的訪問時間是保證在對於任何實施，當前和未來來說最差的O（lg N），但是通常是O（1）（恆定時間）。類似地，線性搜索操作的最壞情況複雜度爲O（N * lg N），儘管通常邊界將更加緊密，依此類推。在一些實現中，插入或刪除操作將典型地在陣列中的值的數量上是線性的，但在最壞的情況下明顯可以是O（N * 1/N）。陣列內部對於表演沒有好處; 也就是說，訪問具有低索引的值或者插入或刪除具有高索引的值或任何值都不一定更快。

這些時間複雜性表明CFArray（因此NSArray）實際上可能爲一棵樹來實現（測試表明，它甚至可能多的基礎數據結構之間進行切換）。

類似地，對於CFDictionary，給定的界限具有相當寬的範圍：

計算複雜

在字典中的值的訪問時間是保證在最壞O（N），用於任何實現，當前和未來，但往往是O（1）（恆定時間）。插入或刪除操作通常也將是恆定時間，但在一些實現中最壞的情況是O（N * N）。通過密鑰訪問值比直接訪問值更快（如果有任何這樣的操作）。與具有相同數量值的數組相比，字典傾向於使用更多的內存。

我沒能找到的核心基礎標題爲CFSet了類似的評論，但是源代碼的檢查表明，它是基於CFBasicHash，這是一個哈希表，所以時間複雜度將是典型的對於散列表 - O（1）插入，刪除和測試通常，並在最壞的情況下O（n）。

如果您真的有興趣瞭解這些數據結構究竟如何工作，Core Foundation是開源的，因此您可以閱讀Apple's website上的源代碼。

來源

2014-10-05 09:24:23 Greg

什麼是通過NSSet和NSDictionary進行迭代的大O符號

回答

相關問題