こんにちは、String クラスの「replaceAll」関数の時間計算量を知りたいのですが、情報が見つかりません。( http://docs.oracle.com/javase/6/docs/api/ java/lang/String.html )
Java が複雑さを Javadoc に含めた方がよいのではないでしょうか? 誰かが知っていることは非常に重要なことだと思います。
4994 次
5 に答える
9
ほとんどの関数は、かなり単純な時間の複雑さを持っています。私の知る限り、replaceAllはO（n）です
私見では。使用するメソッドの 99% がアプリケーションのパフォーマンスにほとんどまたはまったく影響を与えない可能性が高いため、プロファイラーなどを使用して経験的に自分でテストすることに勝るものはありません。
于 2012-04-10T15:40:27.883 に答える
3
保証されている場合、複雑さは文書化される場合があります。たとえば、一部のコレクション クラスでは、複雑さの保証が文書化されています。たとえば、HashMapから:
この実装は、基本的な操作 (get および put) に対して一定時間のパフォーマンスを提供します...
ただし、次のような複雑な場合もあります。
- 保証されておらず、実装の変更により自由に変更できます。
- 明らかにO（1）。
于 2012-04-10T15:40:16.247 に答える
1
Java API の javadoc は、各メソッドで何を実行する必要があるかについての一般的な規約を指定します。方法ではありません。API の各実装者 (たとえば、OpenJDK、Oracle の JDK など) には、各コントラクトの実装方法について一定の自由があり、その自由には、最適化を行うことや、パフォーマンスを犠牲にすることさえ含まれる場合があります。そのため、メソッドが特定のパフォーマンス要件を満たすためにどうしても必要な場合を除き、Javadoc では一般に、関数の時間や複雑さなどの詳細は指定されていません。
于 2012-04-10T15:41:05.107 に答える
0
一般的な答えは、複雑さは通常、分析が難しすぎる要因に依存するというものです。これは確かに に当てはまりString.replaceAll、効果的な複雑さは文字列に大きく依存しregexます。(正規表現の設計が悪いと、マッチングが非常に遅くなる可能性があります。)
于 2012-04-10T15:58:18.870 に答える
0
基本的な操作の空間/時間の複雑さを使用して設計上の決定を行っている場合は、ほぼ間違いなく間違っています。
最初に正しいアプリケーションをビルドしてから、プロファイルを作成します。次に、プロファイリング プロセスで明らかになったボトルネックを最適化します。
于 2012-04-10T15:45:36.293 に答える