java - イテレータの償却複雑度

Question

O(1+log(N/M)) の償却複雑度を持つ AVL ツリーなどのバランスの取れたツリーのために、Java でイテレータ関数を実装する必要がありますが、これが何を意味するのかわかりません。リンクや説明は非常に役立ちます..ありがとう

Answer 1

これは、反復子のメソッドを連続して呼び出すたびにnext()、そのメソッド呼び出しの複雑さが減少することを意味します。N 個のノードを持つツリーの場合、最初の呼び出しは O(log(N)) の複雑さを持つ必要があり、次の呼び出しは O(log(N/2)) を持つ必要があります。複雑さを本当に理解するには、いくつかの背景が必要です。数学とコンピューターサイエンス。短くてあいまいな説明については、こちらをお読みください。このトピックをより深く理解するには、Corman のアルゴリズム入門から始める必要があります。