2017-06-13 11 views
0

私は、スキップリストの挿入時間の複雑さは非常に高い確率で(log n)、最悪の場合にはO(n)の順序であることを読んだ。しかし、redis zaddのドキュメントを読んでいる間は、https://redis.io/commands/zaddというメッセージが表示されます。各アイテムのO(log(N))が追加されます。Nはソートされたセットの要素の数です。zaddのredisでの時間複雑さ

redisがスキップリストを使用する場合、最悪の場合zaddはO(n)にする必要がありますか?

ps:申し訳ありませんが、以前は同じ質問を投稿しましたが、回答はありませんでした。 これを削除して再度作成します。

答えて

0

Redisの実装skiplistは、ウィリアムPughの論文の変更です。したがって、最悪の場合、時間の複雑さはO(n)です。 AVERAGE時間複雑度ZADDO(log(n))です。