Θ记号

图3-1

O记号

Ω记号

定理 3.1

o记号

练习

1.相对渐近增长

2.根据渐近增长率排序

3.渐近记号的性质

4.

Consider sorting n numbers stored in array A by first finding the largest element of A and exchanging it with the element in A[n]. Then find the second largest element of A, and exchange it with A[n-1]. Continue in this manner for all n elements of A. Write pseudocode for this algorithm, and answer the following questions:

What loop invariant does this algorithm maintain?

Give the best-case and worst-case running times of selection sort in asymptotic notation.

考虑通过首先找到A的最大元素并将它与[n]中的元素进行交换来排序存储在数组A中的N个数。然后找到A的第二大元素，并将其与A[n-1]交换。以这种方式对A的所有n个元素继续。为此算法编写伪代码，并回答以下问题：

这个算法保持什么循环不变量？

用渐近表示法给出选择排序的最佳和最坏情况运行时间。