TreeSetの時間複雑度についてprevious questionを読んだところ、答えはO（n）時間かかるということでした。しかし、なぜO（n * nlogn）の代わりにそれが繰り返すのがO（n）なのか分かりません。なぜO（n * logn）ではなくTreeSet Iteration O（n）ですか？
それぞれ次の呼び出しは、私はこのようなTreeSetのを反復処理のであればO(logn) time
を取ります
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）時間がかかります。
1つのnext操作の最悪の時間は、それがツリーの高さのためO(log n)です。しかし平均して、次の要素は時刻O(1)にあります。これは、本質的にトラバーサル全体が、ツリーの各エッジを2回ずつ使用するためです。
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'になります。しかし、Big-Oは平均的ではなく最悪の場合ではないか？ – markspace
@markspace Big-Oは、複雑さ自体ではなく、機能の成長に関するものなので、あなたが望む動作を記述します。平均、最悪ケース、償却、期待コストを高い確率で記述することができます。このケースでは、すべての操作でTheta（n）（最悪のケースと最善のケース）も一緒です。単一の後継者を見つけることはlog n時間を要するかもしれないが、n個の要素のコストは最大で2n回繰り返す。 –
@markspace緻密なビッグオーバーは、最悪の場合の実行時間を指しますが、ビッグオー記法は関数に関する数学的記述に過ぎません。 –
あなたはこのようなツリーに対して反復処理を実装できます。
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）であるので、すべてのノードに対して1回だけ呼び出されようとしています。正確に同じアルゴリズムを反復的に（再帰なしで）実装することができます。また、慎重であれば、繰り返しの状態を維持し、.next()が呼び出されるときに進むクラスを持つことができます。 printlnの間の関数呼び出しの数が不均一であることは事実ですが、全体的に見ると、それらのNが正確にあることがわかります。
なぜiterator.next（）はO（log n）なのですか？それは次のノードに行く必要があります、これはO（1）ですね。 –
@JoseLuisはソースコードを見て正確ではありません。 –
@ louis-wassermanあなたは正しいです、非常に残念です。私はiterator（）がソートされたノードを持つリストを返すことができたと思って、次のノードに行くのは簡単です。 –