最坏情况时间复杂度

习题预习

1. 一个未排序的阵列中找到最大的元素的时间复杂度是多少？
2. 在一个含有n个元素的已排序阵列中，找到一个元素的时间复杂度是多少？
3. 在一个树形结构中，找到最深的叶子节点的时间复杂度是多少？
4. 在一个包含n个元素的无序二元搜寻树中，找到最大或最小的元素的时间复杂度是多少？
5. 在一个n x n的矩阵中，找到最小值或最大值的时间复杂度是多少？

说明知识

Worst-Case Time Complexity指的是在最劣情况下程序的时间复杂度。即在所有可能的输入中，程序需要最长的时间才能完成。

举例来说，如果我们要对一个数组进行排序，并且该数组已经是有序的，那么一个时间复杂度较差的排序算法可能需要O(n^2)的时间才能完成排序。这是因为在有序数组中，该算法仍然需要比较和交换元素，但实际上这些操作是完全不必要的，因为数组已经排序好了。因此，我们可以说在这种情况下，该排序算法的最劣时间复杂度为O(n^2)。

另一个例子是搜索一个数组中是否存在一个元素。如果该元素在数组的开头，则算法可以在常数时间内完成。但如果该元素位于数组的末尾，那么该算法可能需要遍历整个数组才能找到该元素。在这种情况下，该算法的最劣时间复杂度为O(n)。

条列重点

Worst-Case Time Complexity是衡量算法效率的重要指标，指的是当算法面对最差情况时所需执行的最长时间。以下是Worst-Case Time Complexity的重点：

1. 最坏情况：Worst-Case Time Complexity是从理论上判断算法效率的指标，它要考虑所有可能的输入，并选取对算法耗时最长的那一种情况衡量效率。

2. 常见符号：通常用大O符号来表示Worst-Case Time Complexity，例如O(n)、O(logn)、O(n^2)等，它们分别表示当输入规模为n时最坏情况下算法需要执行的时间；

3. 算法效率差距：同一个问题可以有不同的算法，它们的Worst-Case Time Complexity也可能截然不同，因此在选择算法时必须特别注意该算法的时间复杂度；

4. 适用范围：Worst-Case Time Complexity可以帮助我们找到最高效的算法，但也需要注意实际应用中的各种限制因素，例如硬体性能等；

5. 进一步评估算法表现：在实际情况下，算法的表现往往不仅与Worst-Case Time Complexity有关，还需要考虑其他因素，例如最好情况、平均情况等等。因此，对于一个算法的评估还需要综合各种情况进行评估。

知识测验

1. Bubble Sort (冒泡排序) - Worst-Case Time Complexity: O(n^2)

2. Insertion Sort (插入排序) - Worst-Case Time Complexity: O(n^2)

3. Selection Sort (选择排序) - Worst-Case Time Complexity: O(n^2)

4. Naive String Searching (字符串匹配搜索) - Worst-Case Time Complexity: O(m(n-m+1)), 其中m为模式串的长度，n为文本串的长度

5. Quick Sort (快速排序) - Worst-Case Time Complexity: O(n^2)

答案：

1. Bubble Sort: 按照从小到大的顺序排序数组[10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

时间复杂度为n^2，其中n为数组长度，这里为10，最坏情况需要比较45次，移动45次

2. Insertion Sort: 按照从小到大的顺序排序数组[10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

时间复杂度为n^2，其中n为数组长度，这里为10，最坏情况需要比较45次，移动45次

3. Selection Sort: 按照从小到大的顺序排序数组[10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

时间复杂度为n^2，其中n为数组长度，这里为10，最坏情况需要比较45次，移动45次

4. Naive String Searching: 在字符串"ABABABABAB"中搜索模式串"ABAB", “ABAB"每个字符都匹配，但每次匹配都失配，时间复杂度为4*(10-4+1)=28

5. Quick Sort: 按照从小到大的顺序排序数组[10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

序列每次选择第一个元素为枢轴，而序列本身是逆序的，所以每次划分都到了最差情况，时间复杂度为n^2，其中n为数组长度，这里为10，最坏情况需要比较45次，交换45次