c++ - アルゴリズムの複雑さにおけるメモリ使用量の影響

Question

C++STL アルゴリズムに関する Nicolai Josuttis の本を読んでいます。stable_sort() などの多くのアルゴリズムでは、アルゴリズムの複雑さは、十分なメモリが利用可能な場合は n * log(n)、そうでない場合は n * log(n) * log(n) であると述べています。私の質問は、メモリ使用量が複雑さにどのように影響するかです。そして、STL はそのような状況をどのように検出するのでしょうか?

Answer 1