gpt4 book ai didi

algorithm - 计算插入排序的运行时间

转载 作者:塔克拉玛干 更新时间:2023-11-03 06:32:27 28 4
gpt4 key购买 nike

INSERTION_SORT (A)

FOR j ← 2 TO length[A] //c1*n
key ← A[j] //c2*(n-1)
i ← j − 1 //c3*(n-1)
WHILE i > 0 and A[i] > key //c4*sigma(j=2 to n)of(tj)
A[i +1] ← A[i] //c5*sigma(j=2 to n)of(tj-1)
i ← i − 1 //c6*sigma(j=2 to n)of(tj-1)
A[i + 1] ← key //c7*(n-1)

c1、c2、c3、c7 完全有意义。没有意义的是为什么:

c4*sigma(j=2 to n)of(tj) becomes c4*sigma(j=2 to n)of(j)

假设我们正在计算大小为 5 的数组的最坏情况。上面这行说的是第 4 行的时间是:

c4*(1+2+3+4)

实际上是这样的:

c4*((1)+(1+2)+(1+2+3)+(1+2+3+4))

我错过了什么?我知道这本书一定是对的。

编辑搞砸了,应该是:

 c4*((1)+(1+1)+(1+1+1)+(1+1+1+1))
=c4*(1+2+3+4)

最佳答案

但是第 4 行的时间 2 + 3 + 4 + 5。第一次 (j = 2) 是 2 (i = 1 and i = 0)。第二次(j = 3),是3(i = 2, i = 1, i = 0)...

关于algorithm - 计算插入排序的运行时间,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12548860/

28 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com