重複の可能性:
C++ string::find complex
STL の文字列ライブラリに組み込まれている検索操作の時間の複雑さはどれくらいですか?
8764 次
3 に答える
3
標準、§21.4.7.2 は、複雑さに関して何の保証も与えていません。
std::basic_string::findただし、単純なアルゴリズム（各部分文字列が等しいかどうかを確認する）でさえその複雑さを持っているため、検索される文字列の長さに線形の時間がかかると合理的に想定できます。また、std::stringコンストラクターが何かを有効にするために派手なインデックス構造を構築する可能性は低いそれよりも速く。
検索されるパターンの複雑さは、実装に応じて、線形と一定の間で合理的に異なる場合があります。
于 2012-12-10T11:36:02.660 に答える
0
コメントで指摘されているように、標準はそれを指定していません。
ただし、std::stringは一般化されたコンテナであり、保持する文字列の性質については何も想定できない O(n)ため、単一のを検索する場合は複雑になると合理的に想定できますchar。
于 2012-12-10T11:40:20.870 に答える
-3
最大で、範囲 [first,last) 内の要素の数と同じ数の比較を実行します。
于 2012-12-10T11:33:28.550 に答える