当前位置: 首页 > news >正文

网站上的图片一般多大合适/百度电脑版网页

网站上的图片一般多大合适,百度电脑版网页,网站可以个人做吗,南通建设网站哪家好在统计学中,中值往往比平均值更能体现一组数据的特点,因为不会被两边的极端数据影响。 那么要找到一个无序数组的中值,可以先将数组中的数据排序,然后直接返回数组中间的数据即可,但是我们要想到,仅仅只是…

在统计学中,中值往往比平均值更能体现一组数据的特点,因为不会被两边的极端数据影响。

那么要找到一个无序数组的中值,可以先将数组中的数据排序,然后直接返回数组中间的数据即可,但是我们要想到,仅仅只是为了找到数组的中值,就对其进行排序,可想而知时间复杂度会很高,因此这就需要一个更好的算法来求出中值。

算法原理

首先我们可以想一想,如果已知一个数组的中值的位置为k且中值的值也已知,那么从数组的开头开始遍历,如果数组元素大于中值,那么去掉该元素之后,中值在数组中的位置依旧为k;若数组元素小于中值,那么去掉该元素之后,中值在数组中的位置就变成了k-1。这一点需要想明白,不明白的可以在纸上比划比划。

这种思想,我们可以发现其实减治法中的减可变规模。具体可以参考我的另一篇博文:《减治法》

因此,我们可以采用快速分区的思想,但是对于一个无序数组而言,我们并不知道中值是多少,因此这里我们可以假设数组的第一个元素为中值,然后从第二个元素开始,若大于第一个元素,则直接去看下一个元素;若小于第一个元素,则将该元素

先上伪代码

因为伪代码没有其他语言的语法限制,能够有助于我们更好地将注意力放在算法上,所以这里我们先用伪代码来讲述一下主要思想:

首先需要一个划分算法,这里介绍Lomuto划分算法:

algorithm lomutoPartition(A[l..r])
//采用Lomuto算法,用第一个元素作为中轴对子数组进行划分
//输入:数组A[0..n-1]的一个子数组A[l..r],它由左右两边的索引l和r(l <= r)定义
//输出:A[l..r]的划分和中轴的新位置
p <- A[l]
s <- l
for i <- l+1 to r doif A[i] < ps <- s + 1swap(A[s], A[i])
swap(A[l], A[s])
return s

注意:这里的划分算法并不是排序,只是将小于p的元素放到p的左边,大于p的元素放到p的右边,同时s表示的即为元素p在数组中是第s小的元素。

然后使用快速选择算法:

algorithm quickSelect(A[l..r], k)
//用基于划分的递归算法解决选择问题
//输入:可排序数组A[0..n-1]的子数组A[l..r]和整数k(1 <= k <= r-l+1)
//输出:A[l..r]中第k小元素的值
s <- lomutoPartition(A[l..r])
if s = l+k-1 return A[s]
else if s > l+k-1 quickSelect(A[l..s-1], k)
else quickSelect(A[s+1..r], l+k-1-s)

因为已经知道了第一个元素是数组的第s小的元素,则若s刚好等于k,那么就直接返回即可;若s大于k,说明第k小的元素在左侧,那么将s后面的元素删除之后,原来第k小的元素依旧是剩下数组中的第k小的元素,因此就有了quickSelect(A[l..s-1], k)这段;若s小于k,说明第k小的元素在右侧,这个时候我们要注意了!比如一个数组是1、2、3,我要找到第3小的元素,那么假设s=2,k=3,去掉s之前的元素之后,数组就只剩下一个3了,因此我要找的元素就变成了第1小的元素,即k-s,也即伪代码中的quickSelect(A[s+1..r], l+k-1-s)

这里我们可以用一个例子来体会一下:

在数组{4,1,10,9,7,12,8,2,15}中,求第k=5小的元素。

则算法运行步骤为:

数组 {4,1,10,9,7,12,8,2,15} 分区, 中轴=4
分区得:{1,2},{4},{ 9,7,12,8,10,15}, s1=3因s1<k, 在{ 9,7,12,8,10,15} 中找 k-s1=2
分区得:{7,8}, {9}, {12,10,15}, s2=3因s2>k-s1, 在{7,8}中继续找 k-s1=2,
分区得:{7}, {8}, s3=1因s3<k-s1, 在{8}中找 k-s1-s3=1
得,s=k=5, 中值是8

代码实现

那么我们就用代码来实现这一思路,这里我用的是C++:

快速分区部分:

int lomutoPartition(int* A, int low, int high) {int p = A[low];int s = low;for (int i = low + 1; i < high; i++) {if (A[i] < p) {swap(A[i], A[++s]);}}swap(A[s], A[low]);return s;
}int quickSelect(int* A, int low, int high, int n) {int s = lomutoPartition(A, low, high);if (s == n - 1) return A[s];  //具体代码中因为是从0开始,所以第k小元素就是第k-1小元素else if (s > n - 1) quickSelect(A, low, s, n);else quickSelect(A, s + 1, high, n);
}

然后在main函数中启动:

int main() {int A[10] = { 7, 4, 98, 65, 34, 23, 54, 2, 1, 37 };cout << "第3小的元素为:" << quickSelect(A, 0, 10, 3) << endl;cout << "第8小的元素为:" << quickSelect(A, 0, 10, 8) << endl;return 0;
}

运行结果如下:

在这里插入图片描述

时间复杂度分析

最优情况:即进行一次划分之后就直接找到了第k小的元素,则复杂度为
Cbest(n)=n−1∈O(n)C_{best}(n)=n-1\in O(n) Cbest(n)=n1O(n)

最差情况:即数组每次划分都是划分成1个小于p,剩下的大于p,或者反过来,则此时的复杂度为
Cworst(n)=(n−1)+(n−2)+...+1=n(n−1)2∈O(n2)C_{worst}(n)=(n-1)+(n-2)+...+1=\frac{n(n-1)}{2}\in O(n^2) Cworst(n)=(n1)+(n2)+...+1=2n(n1)O(n2)

可以看出,最优情况和最差情况的复杂度差距还是比较大的。

参考资料

《算法设计与分析基础》第三版以及老师的课件

http://www.lbrq.cn/news/1311589.html

相关文章:

  • 青岛建手机网站公司/优化疫情防控
  • wordpress 最快的版本/网站优化包括哪些内容
  • 长沙网站优化外包/实时热榜
  • 昔阳做网站公司/seo怎么做推广
  • 梅州免费建站/网络营销外包收费
  • 网站产品页排名怎么做/seo入门教程视频
  • 做服装外单的网站/seo顾问多少钱
  • 前海网站建设/互联网营销案例
  • 沈阳微信网站制作价格/shodan搜索引擎
  • 沧州有做网站的吗/友情链接交换要注意哪些问题
  • seo网站建设是什么意思/百度引流推广怎么做
  • 政府网站都是谁做的/关键词代发排名首页
  • 在线做网站视频在线观看/拍照搜索百度识图
  • 做网络传销网站犯法吗/网站seo什么意思
  • 建设网站公司哪好/网站优化关键词价格
  • icp网站建设/app下载推广平台
  • 乌兰察布做网站/google seo是什么啊
  • 广州市做网站的/合肥网站推广电话
  • 自定义网站建站公司/搜狗网址
  • 设计网站价格/sem论坛
  • 中小企业网站开发/百度seo手机
  • 怎么建立淘宝客网站/余姚网站seo运营
  • 平定住房建设局网站/软文标题写作技巧
  • 张家口人社app最新下载/城市分站seo
  • wordpress 素材网站模版/六种常见的网络广告类型
  • 什么网站可以做软件有哪些东西/推广赚钱软件排行
  • 济南专业网站推广服务热线/精准引流的网络推广方法
  • 门户网站都在哪推广/武汉网站seo推广公司
  • 怎么做重庆时时彩网站代理/中山做网站推广公司
  • 做网站用笔记本电脑/5118数据分析平台
  • OpenCV中常用特征提取算法(SURF、ORB、SIFT和AKAZE)用法示例(C++和Python)
  • 一个项目的完整一生 --- 一 窗口大小设置
  • 【代码】基于CUDA优化的RANSAC实时激光雷达点云地面分割
  • 搭建云途YTM32B1MD1芯片VSCODE+GCC + Nijia + Cmake+Jlink开发环境
  • QT技巧之快速搭建串口收发平台
  • 算法入门:BFS与DFS详解(C++实现)