2614: 分治策略-线性时间选择
金币值：3
定数：6
时间限制：1.000 s
内存限制：128 M
正确：4
提交：4
正确率：100.00% 命题人：
题目描述
从一个长度为n的顺序线性表中查找第k（1<=k<=n）个小元素，要求平均时间复杂度为O(n)。
测试代码 复制
#include"stdio.h"
int partition(int a[], int left, int right) {
int i=left, j=right;
int x=a[left];
while(i<=j) {
while(a[i]<=x && i<=j) i++;
while(a[j]>x && i<=j) j--;
if(i<=j) {
int t=a[i];
a[i]=a[j];
a[j]=t;
i++;
j--;
}
}
a[left]=a[j];
a[j]=x;
return j;
}
int select(int a[], int left, int right, int k) {
if(left==right) return a[left];
else {
}
}
int main(void) {
int a[100],i,n,k;
scanf("%d",&n);
for(i=0; i<n; i++) scanf("%d",&a[i]);
scanf("%d",&k);
int result=select(a,0,n-1,k);
printf("%d\n",result);
return 0;
}输入格式
第1行输入一个整数n，表示线性表的长度
第2行输入n个整数，表示线性表中存储的具体数据
第3行输入一个整数k，表示需要查找的第k个小元素
第2行输入n个整数，表示线性表中存储的具体数据
第3行输入一个整数k，表示需要查找的第k个小元素
输出格式
第4行输出一个整数，表示第k个小元素的值
输入样例 复制
5
4 3 1 5 6
2输出样例 复制
3提示
思考题：请分别计算以下递推公式时间复杂度
T(n)=T(n/2)+O(1); T(1)=1 二分查找
T(n)=2T(n-1)+O(1); T(1)=1 汉诺塔
T(n)=T(n-1)+O(1); T(1)=1 计算n!
T(n)=2T(n/2)+O(n); T(1)=1 归并排序，快速排序
T(n)=T(n-1)+O(n); T(1)=1 快速排序最坏情况
T(n)=T(kn)+O(n); T(1)=1 线性时间选择(0<k<1)
T(n)=T(n/2)+O(1); T(1)=1 二分查找
T(n)=2T(n-1)+O(1); T(1)=1 汉诺塔
T(n)=T(n-1)+O(1); T(1)=1 计算n!
T(n)=2T(n/2)+O(n); T(1)=1 归并排序，快速排序
T(n)=T(n-1)+O(n); T(1)=1 快速排序最坏情况
T(n)=T(kn)+O(n); T(1)=1 线性时间选择(0<k<1)