插入排序的运行时间 [英] The running time of Insertion-Sort

问题描述

在我的书中，他们计算了输入 n 的插入排序的运行时间.算法是:

In my book they have calculated the running time of insertion sort on an input of n. The algorithm is:

Insertion-Sort(A)                        cost   times
1. for j <- 2 to length[A]                c1    n
2.     do key <- A[j]                     c2    n-1
3.         Insert A[j] into the           0     n-1
            sorted sequence A[1..j-1]
4.     i <- j - 1                         c4    n-1
5.     while i > 0 and A[i] > key         c5    sum_{j=2}^n t_j
6.         do A[i+1] <- A[i]              c6    sum_{j=2}^n (t_j-1)
7.         i <- i - 1                     c7    sum_{j=2}^n (t_j-1)
8.     A[i+1] <- key                      c8    n-1

我的问题是为什么第 1 行的 times=n ?为什么不是 n-1 次?

And my problem is why the times=n in line 1? Why isn't it just n-1 times?

推荐答案

从 C 中的 for 循环的角度考虑:

Think about it in terms of a for loop in C:

for (int i = 2; i <= length(A); ++i) ...

这一行达到了 n 次——一次用于初始化，n - 1 次用于增量和测试.

This line is reached n times — once for the initialisation, and n - 1 times for the increment-and-test.

这篇关于插入排序的运行时间的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！