7

私はさまざまな論文を調べましたが、収集した情報は次のとおりです。

  • SGI 実装とC コードは、長いロープの O(1) 時間の連結も、短いロ​​ープの ~log N 深度も保証しません。
  • 異なる情報源は互いに矛盾しています。ウィキペディアは O(1) 連結を主張しています。このページでは、連結は 1 つのオペランドが小さい場合のみ O(1) であり、それ以外の場合は O(log N) であると述べています。

では、連結の時間計算量はどのくらいですか? ツリーのバランスを維持しながら、この連結の複雑さを確保するために正確にリバランスが実行されるのはいつですか? この複雑さについて話すとき、いくつかの特定の使用パターンが想定されていますか?

4

1 に答える 1

3

ウィキペディアの記事は不明確であり、どこにも引用されていない論文「Ropes: an Alternative to Strings」は、そのような複雑な結果を主張しています。

一方、この最近の論文 (Gerth Stølting Brodal、Christos Makris、および Kostas Tsichlas による)は次のことを行っています。彼らはO(logn)検索も持っているので、実際に「バランス」とタグ付けすることができます。詳細は読んでいませんが、結果だけです。

「ロープ」は、実際には（比較的）一般的な用語ですが、研究では一般的ではありません。代わりにcatenable queues、特にタージャン、オカサキ、カプランなどの人々によって行われた調査（またはリスト）を検索しました。それがあなたの本当の答えだと思います.

于 2010-10-13T16:20:33.520 に答える