# Q：计算一个未排序的数组的一部分找到一个高效的算法

The question is:

Given an array of n unsorted elements. For each of the following value of k, suggest an efficient algorithm in terms of worst case complexity for computing the k minimal values where:

a. k = 30

b. k = n/3

c. k = logn

For each case, give a short description of the algorithm and brief analysis of the worst and the best case complexity. Edit: We don't have to sort the unsorted array, as long as we compute k in an efficient way, it's fine.

Ok, so I am not sure of this at all,

a) For k = 30, I would suggest that we will find the minimal number 30 times, for the first time we will run n times, for the second time it will be n - 1, until n - 29. so way we can compute the 30 lowest numbers in O(n), (right?)

b) Thinking about just sorting it in an nlogn worst case sorting algorithm (heapsort or mergesort, depends on if the user will or will not want to use extra space) and then just compute the first n/3, so I can do this in O(nlogn) steps.

c) Thought about making a min heap from this array, so to heapify it will cost me O(n), after that I need to use the deleteMin of the heap (that will cost me O(logn) exactly logn times so it will be n + logn^2 which means O(n) (right?)

Given an array of n unsorted elements. For each of the following value of k, suggest an efficient algorithm in terms of worst case complexity for computing the k minimal values where:

k = 30

C. K = LOGN

For each case, give a short description of the algorithm and brief analysis of the worst and the best case complexity. Edit: We don't have to sort the unsorted array, as long as we compute k in an efficient way, it's fine.

a) For k = 30, I would suggest that we will find the minimal number 30 times, for the first time we will run n times, for the second time it will be n - 1, until n - 29. so way we can compute the 30 lowest numbers in O(n), (right?)

b) Thinking about just sorting it in an nlogn worst case sorting algorithm (heapsort or mergesort, depends on if the user will or will not want to use extra space) and then just compute the first n/3, so I can do this in O(nlogn) steps.

C）从这个数组做一个最小堆的思想，所以它将花费我Heapify（N），之后我需要使用堆（那将花费我DeleteMin O（logN）完全logN次就N logN ^ 2这意味着O（N）（右？）