Express the function
in terms of Θ-notation.
Θ(n^3)
Consider sorting n numbers stored in array A by first finding the smallest element of A and exchanging it with the element in A[1]. Then find the second smallest element of A, and exchange it with A[2]. Continue in this manner for the first n - 1 elements of A. Write pseudocode for this algorithm, which is known as selection sort. What loop invariant does this algorithm maintain? Why does it need to run for only the first n - 1 elements, rather than for all n elements? Give the best-case and worst-case running times of selection sort in Θ- notation.
Loop invariant: at the start of each iteration of the outer for loop, the subarray A[1..j-1] consists of the j-1 smallest elements in the array A[1..n] and this subarray is in sorted order.
After the first n-1 elements, the subarray A[1..n-1] contains the smallest n-1 elements, sorted, and therefore element A[n] must be the largest element
时间都是Θ()
Consider linear search again (see Exercise 2.1-3). How many elements of the input sequence need to be checked on the average, assuming that the element being searched for is equally likely to be any element in the array? How about in the worst case? What are the average-case and worst-case running times of linear search in Θ-notation? Justify your answers.
-
平均情况应该要查找(n+1)/2个元素
-
最坏情况是n个
-
Assuming equal probability of occurrence 1/n, average number of elements which need to be checked is 1/n * (1 + 2 + ... +n) = (n+1)/2. Running time is Θ(n)
-
Worst case, the element to search is dead last in the array. In that case n elements need to be searched. Running time is Θ(n)
所以都是Θ(n)
How can we modify almost any algorithm to have a good best-case running time?
算法开始检测输入数据，若符合特殊条件则输出事先计算好的结果
Modify the algorithm so it checks whether the input satisfies some special case condition. If it does, output a pre-computed answer.
Follow @louis1992 on github to help finish this task.