＞第 11 章 排序与查找＞线性查找＞习题

习题中的第三题找第K小的算法还是nlng的复杂度啊，partition的复杂度是n没错，后面的递归调用跟前面的快排比起来，无非是两个递归分支变成一个递归分支了，复杂度还是一样的啊。。真奇怪
然后我查看了MIT的课程，它用的是随机划分，伪代码是
Randomized-Partition(A, p, q)
  swap(A[p], A[rand(p,q)]) // the only thing changed in the original Partition subroutine!
  x = A[p]
  i = p
  for j = p+1 to q
    if A[j] <= x
      i = i+1
      swap(A[i], A[j])
  swap(A[p], A[i])
  return i


Randomized-Select(A, p, q, k) // finds k-th smallest element in array A[p..q]
  if p == q
    return A[p]
  r = Randomized-Partition(A, p, q)
  n = r - p + 1
  if k == n
    return A[r]
  if k < n
    return Randomized-Select(A, p, r-q, k)
  else
    return Randomized-Select(A, r+1, q, k-n)

两个分支变成一个分支了，时间复杂度还是一样的？那是你想当然的。你再仔细想想能一样吗。另外，算法导论上应该有这个时间复杂度的分析。本书是一本基础书，不能在这方面深入展开了。

确实，在第几次循环return是不确定的，因此乘上概率，这样粗略能降一次。树的最大深度是Θ(n),单支，算法果然要慢慢想，哎。

你可以这样想（假设每次找到的pivot都刚好是中点）：
找第k小的算法，每次丢掉一半，第一层处理n个，第二层处理n/2个，第三层处理n/4个……一共处理n+n/2+n/4+...=2n个，所以是Θ(n)
快速排序，第一层处理n个，第二层分两组，每组处理n/2个，加起来还是n个，同理，第三层也是n个，每层都处理n个，一共处理lgn层，所以是Θ(nlgn)

第三题：

#include <stdio.h>
#define N 7
int a[N] = {3, 9, 5, -4, 4, 3, 2};
void exchange(int i, int j){
	int tmp = a[i];
	a[i] = a[j];
	a[j] = tmp;
}

int order_statistic(int start, int end, int k){
	int select = a[end-1];
	int i = start;
	int j = end - 2;
	while (i <= j) {
		while (a[i] < select) i++;
		while (a[j] >= select) j--;
		if (i < j) {
			exchange(i, j);
		} else {
			break;
		}
		i++;
		j--;
	}
	exchange(i, end-1);
	if (k == i) {
		return a[k];
	} else if (k > i) {
		return order_statistic(i+1, end, k);
	} else {
		return order_statistic(start, i, k);
	}
}

	
int main(void){
	int k; 
	scanf("%d", &k);
	int i;
	for (i = 0; i < N; i++) printf("%d ", a[i]);
	printf("\n");
	printf("you find %d of array\n", k);
	printf("the answer is: %d\n", order_statistic(0, N, k));
}

如果不把所有的数查看一遍又怎么能知道最小的数呢？请问怎么样才能达到比O(n)更快呢？

如果考虑预处理的话 那绝对不可能比O(n)还小
而如果不考虑预处理时间，不考虑空间复杂度，那么最快的是哈希 直接O(1)

“从后半部分找出第k-i小的元素并返回” 感觉应该写成“从后半部分找出第k小的元素并返回”比较好理解。
如果按照题面来写的话，就会写成这样了，写成这样结果就不对了:

 	}else if (k > i){
		/* 从后半部分找出第k-i小的元素并返回 */
		return order_statistic(i+1, end, k-i);

	}

--------------------------------
/*
 * 从下标为范围start～end中返回下标为k的数组位置的值
 */
int order_statistic(int start, int end, int k)
{
	/* 用partition函数把序列分成两部分，中间的pivot元素是序列中的第i个 */
	int i=partition(start, end);

	if (k == i){
		/* 返回找到的元素 */
		return a[i];
	}else if (k > i){
		/* 从后半部分找出第k-i小的元素并返回 */
		return order_statistic(i+1, end, k);

		/*
		 * oops!
		 * return order_statistic(i+1, end, k-i);
		 */
	}else{
		/* 从前半部分找出第k小的元素并返回 */
		return order_statistic(start, i-1, k);
	}
}

楼上说得有道理，谢谢

实在想不出对于无序数组的查找，怎么才可以在时间复杂度上小于Θ(n)？

google了二小时了，还是没有找到答案。

有一种查找的效率介于顺序（线性）查找和二分（折半）查找之间，叫做分块查找，又称索引顺序(线性)查找。

但是这种查找是要以有索引表为前提的。而创建索引表的过程时间复杂度也是Θ(n)。

翻了好几本书，都没有找到对于无序数组的查找时间复杂度上小于Θ(n)的。

虽然宋老师也没有说一定有，但是这话看着就是有的意思呀……

宋老师有空的时候，满足下我的好奇心和求知欲吧！

很抱歉误导你了，我这个问题的本意就是想说“没有”。在随机排列的一组数中要找出某个数，至少需要把每个数都检查一遍吧，那么就至少是O(n)。
如果要小于O(n)，就要有一部分数不检查，既然是随机排列的，那怎么保证要找的数不是正好在没检查到的那些数里呢？

第三题中，一组随机排列的数中，有可能存在两个相同的数吗？

如果您有建设性意见，哪怕只是纠正一个错别字，也请不吝赐教，您留下的姓名和email将会出现在本书前言的致谢中。再次感谢您的宝贵意见！