algorithm - アルゴリズムの時間と空間の複雑さの計算

Question

いくつかの並べ替えアルゴリズムのベンチマークを作成し、パフォーマンスを比較する必要があります。だから私が尋ねる必要があるのは、プログラムの時間と空間の複雑さを監視するのに役立つツールがそこにあるかということです. Google で検索しようとしましたが、検索結果が適切な方向に導かれませんでした。事前にサンクス。

Answer 1

@OliCharlesworth がすでに指摘しているように、あなたの質問は時間/空間の「複雑さ」とは何の関係もありません。時間の複雑さは、RAM マシンやチューリングマシンなどの理想的な計算モデルでアルゴリズムが実行するステップ数の漸近的な尺度です。

本当にやりたいことは、アルゴリズムの具体的な実装にかかる時間とスペースの量を測定することです。もちろん、これは、そのために使用している言語によって異なります。実行可能ファイルにコンパイルするものを使用している場合は、Valgrindツール スイート、特に Massif (メモリ プロファイラー) と Callgrind (時間プロファイラー) に興味があるかもしれません。