それはO(1)またはO(logN)ですが、係数は小さいですか?
これが指定されていない場合は、マップ/セットが赤黒または AVL ツリーを使用して実装されているという合理的な仮定に基づいて、少なくとも答えを知りたいと思います。要素を挿入する一般的なアルゴリズムは、次のようなものだと思います。
- 適切な場所を見つける - O(logN)
- 実際の挿入を行います - ?
- 必要に応じてツリーのバランスを取り直します - ?
正しい反復子ヒントを提供すると、最初のステップはO(1)になります。他のステップもO(1)またはO(logN)ですか?