我正在嘗試學習回圈不變技術以產生更有效的演算法。我對通過評估回圈不變數來證明正確性的理解是，回圈不變數在迭代之前和迭代之后必須為真，以確認所需的輸出。
在我放在下面的演算法的情況下（按降序對序列進行排序） - 這是我認為滿足正確性確認的屬性：
“目標將是序列正在減少，使得所有 i 從 0 到 j-1 的 A[j] > A[i]”
我也認為 i >=0 和 i < A.length 在這種情況下是回圈不變數。
在檢查回圈不變數的三個步驟（初始化、維護、終止）時……我想出的東西在這種情況下有意義嗎？我覺得我仍然不太了解如何在這種情況下應用這個概念。
static void Sort(int array[]) {
int size = array.length;
for (int i = 0; i < size - 1; i )
for (int j = i 1; j < size; j )
if (array[j] > array[i]) {
// swapping elements.
int buffer = array[j];
array[j] = array[i];
array[i] = buffer;
}
uj5u.com熱心網友回復：
有一個“背景不變數”表示陣列的內容只是被置換（沒有修改、抑制或添加值）。修改陣列的唯一操作是交換，這一事實保證了不變性。
現在，觀察到內部回圈僅尋址 的元素i，其中i增加。這意味著陣列的初始部分（直到i-1）必須是排序序列的開始。這是外回圈的不變數。所以內部回圈的目的是找到排序序列的下一個元素并將其帶到位置i。
這將我們引向內回圈的不變數，它表示槽i包含迄今為止看到的值中的最小值，即在范圍內i..j。
插圖：
如果我們將演算法應用于陣列
6 8 1 3 4 7 0 9
我們可以肯定，在外回圈執行兩次后，陣列將以
1 3
由于陣列的其余部分可能已被打亂，因此很難預測內部回圈中接下來會發生什么。
無論如何，在外回圈的第一次迭代期間，在內回圈的三次迭代之后，我們知道第一個值將是
1
因為它是最小的
6 8 1
for (int i = 0; i < size - 1; )
// array[0..i-1] is the prefix of the sorted sequence
for (int j = i 1; j < size; )
// array[i] is the smallest among array[i..j-1]
if (array[j] > array[i]) {
// swapping elements.
int buffer = array[j];
array[j] = array[i];
array[i] = buffer;
}
// array[i] is the smallest among array[i..j]
j ;
// array[i] is the smallest among array[i..j-1]
}
// array[0..i] is the prefix of the sorted sequence
i ;
// array[0..i-1] is the prefix of the sorted sequence
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/422814.html
標籤：
上一篇：確定多邊形是否為星形