Code Bye

求无序数组中的最小K个数，划分法时间复杂度是O(n)

码拜
划分 算法 c语言 最小k个数

见《剑指offer》167页。

void GetLeastNumbers(int* input, int n, int* output, int k)
{
	if (input == NULL || output == NULL || k > n || n <= 0 || k <= 0)
		return;
	int start = 0;
	int end = n - 1;
	int index = Partition(input, n, start, end);
	while (index != k - 1)
	{
		if (index > k - 1)
		{
			end = index - 1;
			index = Partition(input, n, start, end);
		}
		else
		{
			start = index + 1;
			index = Partition(input, n, start, end);
		}
	}
	for (int i = 0; i < k; ++i)
		output[i] = input[i];
}

时间复杂度为什么是O(n) ?
#1

1分
这个是使用计数排序的吧？不过，用堆来做个人感觉更常见上些
#2

1分
假设  Partition(input, n, start, end); 为 index++;

那么

for(int index = 0; index < k; index++) ;的时间复杂度为多少?
#3

17分
因为每次递归只进入一边，所以复杂度是 O(n).
#4

回复2楼:

每次 Partition都要扫描一次数组，按照你这种说法时间复杂度就是o(nk)了
#5

1分
象是select 算法, 记忆中应该是期望时间是O(n), 有兴趣翻一下 CLRS顺序统计量那章,上面有证明
#6

回复1楼:

不是计数排序，是用了快排中的划分方法。堆方法适合处理海量数据，性能确实比较好，时间复杂度为o(nlogk)。我现在想知道为什么划分这种方法时间复杂度是o(n) ？
#7

回复5楼:

这是快排中的划分方法。快排必须递归到logn层，而求最小k个数可能只需要划分几次就找到index了。
#8

回复3楼:

是这个道理。在回复别人的时候突然想通了，快排是必须要向下递归的，而上面这个并不需要递归，而是类似折半。

1+1/2+1/4+1/8+…<2    ，o(2n)=o(n)，所以时间复杂度是o(n)。
CodeBye 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明求无序数组中的最小K个数，划分法时间复杂度是O(n)！