プロジェクトのニーズに非常に適していると思われるTreeRangeMapをグアバしようとしています。java docs は、get、put、および next の時間が O(log(n)) である (Java 標準 ?) TreeMap に基づいていると述べています。
ただし、TreeRangeMap は、このSO の質問によると、クエリの O(k + log(n)) 時間の複雑さ、O(n) スペース、k が範囲サイズである、ある種の範囲ツリー実装である必要があります。誰かがこれを確認できますか？
TreeRangeMap.subRangeMap()操作の時間の複雑さにも非常に興味があります。同じ O(k + log(n)) を持っていますか?
ありがとう。
これはビューであり、実際の突然変異などではありません。subRangeMapは O(1) 時間で戻り、RangeMapそれが返すにはO(log n)クエリ操作ごとに追加のコストがかかります。つまり、そのすべての操作は依然として を要しますがO(log n)、定数係数が高くなります。
出典：私は「それを実装した男」です。
通常、範囲ツリーを使用して、特定の間隔にあるポイントを見つけます[x1, x2] and x1 < x2。ただし、範囲ツリーが (TreeMap赤黒木で実装されている場合のように) バランス バイナリ ツリーである場合、 x1(または後続) およびx2(または先行) への検索パスにはコスト がありますO(log n)。それらを見つけたときにk、ポイントの数がこの範囲内にある場合は、線形コストを持つツリー トラバーサルを使用してレポートする必要がありますO(k)。合計でO(k + log(n))。
TreeRangeMap.subRangeMap() 操作の時間の複雑さにも非常に興味があります。同じ O(k + log(n)) を持っていますか?
<K,V> subRangeMap(Range<K> subRange)この範囲マップの範囲と交差する部分のビューを返し、結果として別のbalanced-binary search Tree. では、なぜですか？