输油管道问题

r); Р swap(a[i],a[p]); Р return Partition(a,p,r); Р} Р利用随机划分来找到中位数Рint RandomizedSelect(int *a,int p,int r,int k) Р{ Р?if(p>=r)return a[p]; Р实验内容(算法、程序、步骤和方法)Р int i = RandomizedPartition(a,p,r), Р j = i-p+1; Р if (k == j)Р return a[i]; Р if(k<j)Р return RandomizedSelect(a,p,i-1,k); Р elseР return RandomizedSelect(a,i+1,r,k-j); Р} Р 交换两个数据Рvoid swap(int &n,int &m)Р{ Р int temp = n; Р n = m; Р m = temp;Р}Р三、复杂度分析Р 如果用教材中的最坏情况下的线性时间选择算法Select计算出中位数,然后计算n口油井到主管道的最小长度和,则所需时间主要是选择算法Select用的时间,在最坏情况下需要O(n*n)计算时间。Р 在本实验中,我采取了随机选择算法RandomizedSelect计算出中位数,平均情况下时间复杂度为O(n)。Р 所需的空间为O(n)。Р数据记录Р和计算Р结论Р(结果)Р 对输入的数据,找出这些数据的差绝对值的和最小的数(即找中位数)。结合随机选择算法计算中位数的方法是输油管问题的最佳解决办法之一。Р小结Р实验心得:首先调用排序算法对所有点的纵坐标,按照从小到大的顺序排好序,我们可以将纵坐标最大和最小的两个点当做一对,纵坐标次大和次小的两个点当做一对,依此类推,那么主管道的位置就落在最中间的那个或是那几个点的纵坐标上。Р指导老师Р评议Р 成绩评定: 指导教师签名: