java 里的循环不变式百度百科_算法中的循环不变式

﹏ヽ暗。殇╰゛Y 2022-11-06 12:59 134阅读 0赞

算法导论中提出的循环不变式，计算机领域解决实际问题的强大方法，值得牢记。

数学基础

循环不变式的数学基础是是数学归纳法

数学归纳法范式

给定命题P(n)

证明当n=1时命题成立

证明如果在n=m时命题成立，那么可以推导出在n=m+1时命题也成立

数学归纳法的原理在于：首先证明在某个起点值时命题成立，然后证明从一个值到下一个值的过程有效。当这两点都已经证明，那么任意值都可以通过反复使用这个方法推导出来。

举例证明

命题

假设我们要证明下面这个公式(命题)：

1+2+3+…+n=\\frac\{n(n+1)\}\{2\}

证明

第一步：n=1时命题成立

1=\\frac\{1(1+1)\}\{2\}

第二步：假设n=m时命题成立

1+2+3+…+m=\\frac\{m(m+1)\}\{2\}

第三步：证明n=m+1时命题成立

1+2+3+…+m+(m+1)=\\frac\{m(m+1)\}\{2\}+(m+1)

上面等式运算最终得到如下等式：

1+2+3+…+m+(m+1)=\\frac\{(m+1)((m+1)+1)\}\{2\}

令k=m+1，则上面等式变为：

1+2+3+…+(k-1)+k=\\frac\{k(k+1)\}\{2\}

这个等式符合第二步的假设，证明完毕。

计算机语言中的循环不变式

计算机语言中的循环不变式由两部分组成：循环，不变式 。

循环：对应到数学归纳法中的1…n

不变式：对应到数学归纳法中的命题

在计算机语言中，通过循环维持命题一直为真，直至循环结束。

按照下面步骤，判断一个算法中的循环不变式的正确性：

初始状态：不变式的命题是否为真

维持不变式：是否维持了不变式继续为真

结束：循环是否正确的结束了

插入排序算法中的循环不变式

算法描述

从未排序的堆中获取一个数，与已排序的序列比较，插入到合适的位置。

以扑克牌为例子，每次从扑克牌堆中获取一张牌，与手中已经排好序的扑克牌比较，找到合适的位置插入到手中的排中。

循环不变式

对于给定的无序序列A\[1…n\]，算法中的不变式为已经排好序的序列A\[1…i\]。

当i=1时，不变式A\[1\]是已经排序好的(因为只有一个元素)，命题成立。

算法中的循环需要保持当i=k时，A\[1…k\]仍然是排序好的，则当循环结束，i=n时，A\[1…n\]是一个排序好的序列。

伪代码

for i =0 to n:

j = i - 1

next = A\[j\]

while j > 0 and A\[j\] > next:

A\[j+1\] = A\[j\] \#大的数网后移动，空出位置j给next

j--

A\[j+1\]=next

i++

python代码

def insertion\_sort(A):

length = len(A)

if length < 2:

return

i = 0

while i < length:

j = i - 1

next = A\[i\]

while j >= 0 and A\[j\] > next:

A\[j+1\] = A\[j\]

j = j - 1

A\[j+1\] = next

i = i + 1

选择排序算法中的循环不变式

算法描述

在一堆未排序的数中，假设为A\[1…n\]，选择一个最小的，放到A\[1\]的位置，再选择一个第二小的，放到A\[2\]的位置。重复上述操作直至所有的数被选择完成，完成排序。

循环不变式

对于给定的无序序列A\[1…n\]，算法中的不变式为A\[1…i\]，A\[1…i\]为每次从无序序列中找出的最小的值组成。

当i=1时，A\[1\]是从A\[1…n\]中找到的最小值，不变式成立。算法中需要保持A\[1…k\]一直是从A\[k,n\]中找到的最小值，当k=n时，A\[1…n\]是排序的序列。

伪代码

for i = 0 to n:

for j = i to n:

\# 从i到n序列中找到一个最小值所在位置k

\# 交换A\[i\]与A\[k\]的值

python代码

def selection\_sort(A):

n = len(A)

if n < 2:

return

i = 0

while i < n:

min = A\[i\]

k = i

j = i + 1

while j < n:

if A\[j\] < min:

min = A\[j\]

k = j

j = j + 1

tmp = A\[i\]

A\[i\] = A\[k\]

A\[k\] = tmp

i = i + 1

冒泡排序算法中的循环不变式

算法描述

给定一个无序序列A\[1…n\]，选定第一个与后面所有值比较，如果比当前值小，则将小的值与当前值交换；依次遍历整个序列，完成排序。

循环不变式

算法中的不变式为A\[1…i\]，当i=1时，遍历剩余n-1个元素与A\[1\]比较，如果A\[k\]>A\[1\]，则交换他们两的值，此时A\[1\]是序列中的最小值。算法中维持此不变式，那么当i＝n是整个序列排序完毕。

伪代码

for i = 0 to n:

for j = i to n:

if A\[i\] > A\[j\]:

swap(A\[i\], A\[j\])

python代码

def bubble\_sort(A):

n = len(A)

if n < 2:

return

i = 0

while i < n:

j = i

while j < n:

if A\[i\] > A\[j\]:

tmp = A\[i\]

A\[i\] = A\[j\]

A\[j\] = tmp

j = j + 1

i = i + 1

归并排序算法中的循环不变式

算法描述

归并排序使用递归的方法实现。假设无序的序列A\[p…q\]被排序为了两个子序列：A\[p…r\], A\[r…q\]，那么最终的有序序列需要将这两个字序列排序，排序方法为：从两个序列分别取一个值，比较大小，合并到最终的序列中，直至两个序列最终合并为一个序列。

循环不变式

合并算法过程中的不变式为A\[p…k\]，A\[p…k\]的值由两个字序列逐个元素比较后得到，过程中保持A\[p…k\]始终是排序后的序列，那么当k=q时整个序列就是排序好的。

伪代码

合并算法分为两部分：合并，递归。

合并部分伪代码

merge(A, p, r, q):

left = A\[p:r\]

right = A\[r:q\]

\#如果left不为空，right为空，则将left所有元素合并到A

\#如果right不为空，left为空，则将right所有元素合并到A

\#否则，逐个比较left与right的元素，合并到A

递归部分伪代码

merge\_sort(A, p, q):

r = (p+q)/2

if q-p > 1:

merge\_sort(A, p, r)

merge\_sort(A,r,q)

merge(A, p, q)

python代码

def \_merge(A, p, r, q):

left = A\[p:r\]

right = A\[r:q\]

\# 结束标记

left.append(None)

right.append(None)

k = p

i = j = 0

while k < q:

if left\[i\] is None and right\[j\] is not None:

A\[k\] = right\[j\]

j = j + 1

k = k + 1

continue

if right\[j\] is None and left\[i\] is not None:

A\[k\] = left\[i\]

i = i + 1

k = k + 1

continue

if left\[i\] < right\[j\]:

A\[k\] = left\[i\]

i = i + 1

else:

A\[k\] = right\[j\]

j = j + 1

k = k + 1

def merge\_sort(A, p, q):

if q - p > 1:

r = (p + q)/2

merge\_sort(A, p, r)

merge\_sort(A, r, q)

\_merge(A, p, r, q)

代码参考

java 里的循环不变式百度百科_算法中的循环不变式

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关 Java性能优化：为什么循环中的变量不提前声明？

相关 java中的泛型、协变、逆变、不变

相关利用循环不变式实习二叉树的层序遍历(LeetCode 102)

相关 java 里的循环不变式百度百科_算法中的循环不变式

相关 NYOJ--中缀式变后缀式

相关 [珠玑之椟]浅谈代码正确性：循环不变式、断言、debug

相关插入排序与循环不变式

相关利用循环不变式写出正确的二分查找及其衍生算法

相关 Kotlin的型变解析（协变、逆变和不变）

相关 java插入排序及循环不变式