Code Bye

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

见《剑指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)