爲什麼TreeSet迭代O（n）而不是O（n * logn）？

我讀了一篇關於TreeSet的時間複雜度的previous question，答案是需要O（n）次。但是，我不明白爲什麼它是O（n）迭代而不是O（n * nlogn）。爲什麼TreeSet迭代O（n）而不是O（n * logn）？

每下一次調用需要O(logn) time

所以，如果我通過一個TreeSet重複這樣的：

while (iterator.hasNext()){ //Runs N times 
    System.out.println(iterator.next() + " "); //each next is O(logn) 
}

我希望它是O（N * LOGN），而不是爲O（n），因爲while循環有N次迭代，每個iterator.next（）調用需要O（logn）時間。

來源

2016-04-14 Eric S

爲什麼'iterator.next（）'是O（log n）。它只需要去下一個節點，這是O（1），不是嗎？ –

@JoseLuis不準確，基於查看源代碼。 –

@ louis-wasserman你說得對，我很抱歉。我認爲iterator（）可以返回一個帶有排序節點的列表，然後去下一個節點很容易。 –

一個next操作的最壞情況時間是O(log n)，因爲那是樹的高度。然而，平均而言，下一個元素可以在時間O(1)中找到。這是因爲整個遍歷實質上使用了兩次樹邊的每一個。

來源

2016-04-14 20:57:02

Iterator.next的代碼似乎最終在'TreeMap.Entry.successor（）'中，在這裏：http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6- b14/java/util/TreeMap.java＃TreeMap.successor％28java.util.TreeMap.Entry％29是的，似乎大多數情況下下一個條目只是'p.left！= null'。但是，大O不是最壞的情況，而不是平均？ – markspace

@markspace Big-O描述了你想要的任何行爲，因爲它本身並不關於複雜性，而是關於函數的增長。您可以高概率地描述平均值，最壞情況，攤銷期望成本，...在這種情況下，所有操作一起都是Theta（n）（最差和最好的情況）。找到一個後繼者可能需要花費時間，但是所有n個元素的迭代成本至多爲2n。 –

@markspace沒有詳細說明的大O界限是指最壞情況下的運行時間，但大O符號只是關於函數的數學表述。 –

您可以實現迭代像這樣的樹：

void print(Node n) { 
    if (n.left != null) print(n.left); 
    System.out.println(n.value); 
    if (n.right != null) print(n.right); 
}

功能打印將被調用一次爲每個節點，所以總的迭代時間爲O（N）。您可以迭代地實現完全相同的算法（無遞歸）。如果你足夠小心，你可以有一個班級保持迭代狀態，並在.next()被調用時提前。確實，println之間函數調用的數量是不平衡的，但是當您從整體上看時，您會發現它們確實有N個。

來源

2016-04-15 07:26:37 Sorin

爲什麼TreeSet迭代O（n）而不是O（n * logn）？

回答

相關問題