algorithm - ループ不変関数

Question

ループ不変式について知りたいです。アルゴリズム（主にソートアルゴリズム）にはループ不変条件があり、ループ不変条件はアルゴリズムの正しさを示していることを知りました。

これはどのように作動しますか？誰かがこれを理解するのを手伝ってくれますか?

Answer 1

ループ不変条件自体は、アルゴリズムの正当性を示すものではありません。これは、ループの各反復に当てはまる述語です。（通常、述語が実際にループに対して不変であることを証明する必要があります。）次に、不変条件を使用して、ループのさまざまなプロパティ（おそらく、正確さを含む）を証明できます。ウィキペディアの記事「ループ不変条件」には、これがどのように機能するかを示すいくつかの例があります。その他の例と説明については、このスレッドを参照してください。