首页 常见问题 线性时间选择

线性时间选择

Jun 20, 2019 am 11:07 AM
时间 线性

线性时间选择

定义:给定线性序集中n个元素和一个整数k,1≤k≤n,要求找出这n个元素中第k小的元素。

(1)在某些特殊情况下,很容易设计出解选择问题的线性时间算法。如:当要选择最大元素或最小元素时,显然可以在O(n)时间完成。(一趟比较即可)

(2)一般的选择问题,特别是中位数的选择问题似乎比最小(大)元素要难。但实际上,从渐近阶的意义上,它们是一样的。也可以在O(n)时间完成。

线性时间选择方法一:randomizedSelect

思想:改编随机快速排序,不用把整个数组全部排序,而是选择的排序(更快)

时间复杂度:

(1)在最坏情况下,算法randomizedSelect需要O(n^2)计算时间

eg.要找最小的元素,但是每次进行Partition函数划分时得到的位置总是很大(靠近n)(即总是在最大元素出划分)

(2)但可以证明,算法randomizedSelect可以在O(n)平均时间内找出n个输入元素中的第k小元素。

代码如下:

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

int Partition(int a[],int p,int r){
    int i=p,j=r+1,x=a[p];
    while(1){
        while(a[++i]<x&&i<r);
        while(a[--j]>x);
        if(i>=j)break;
        swap(a[i],a[j]);
    }
    a[p]=a[j];
    a[j]=x;
    return j;
}

int RandomizedPartition(int a[],int p,int r){
    int i=rand()%(r-p)+p;
    swap(a[p],a[i]);
    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);//返回基准元素的位置
    int j=i-p+1;//表示基准元素及其左边一共多少个元素
    if(k<=j)RandomizedSelect(a,p,i,k);
    else RandomizedSelect(a,i+1,r,k-j);
}
int main(){
    int a[10]={3,1,7,6,5,9,8,2,0,4};
    int x;
    while(scanf("%d",&x)!=EOF){
        int ans=RandomizedSelect(a,0,9,x);
        printf("%d\n",ans);
    }
}
登录后复制

线性时间选择方法二:

如果能在线性时间内找到一个划分基准,使得按这个基准所划分出的2个子数组的长度都至少为原数组长度的ε倍(0<ε<1是某个正常数),那么就可以在最坏情况下用O(n)时间完成选择任务。

例如,若ε=9/10,算法递归调用所产生的子数组的长度至少缩短1/10。所以,在最坏情况下,算法所需的计算时间T(n)满足递归式T(n)≤T(9n/10)+O(n) 。由此可得T(n)=O(n)。

老师讲这时,我记得很清,强调了找到而非确定,“找到”是找到我们想要得中位数的值,而我们之前的快排等都是确定值的位置,即把基准元素放到正确的位置上。

步骤:

(1)将n个输入元素划分成n/5(向上取整)个组,每组5个元素,最多只可能有一个组不是5个元素。用任意一种排序算法,将每组中的元素排好序,并取出每组的中位数,共n/5(向上取整)个。

(2)递归调用select来找出这n/5(向上取整)个元素的中位数。如果n/5(向上取整)是偶数,就找它的2个中位数中较大的一个。以这个元素作为划分基准。

划分策略示意图:

白色圆点:每组的中位数; 点x:中位数的中位数

20180503121832699.png

例子:

按递增顺序,找出下面29个元素的第18个元素:8,31,60,33,17,4,51,57,49,35,11,43,37,3,13,52,6,19,25,32,
54,16,5,41,7,23,22,46,29.
(1) 把前面25个元素分为5(=floor(29/5))组: (8,31,60,33,17),(4,51,57,49,35),(11,43,37,3,13),(52,6,19,25,32),(54,16,5,41,7);
(2) 提取每一组的中值元素,构成集合{31,49,13,25,16};
(3) 递归地使用算法求取该集合的中值,得到m=25;
(4) 根据m=25, 把29个元素划分为3个子数组(按原有顺序)
P={8,17,4,11, 3,13,6,19,16,5,7,23,22}
Q={25}

R={31,60,33,51,57,49,35,43,37,52,32,54,41,46,29}

(5) 由于|P|=13,|Q|=1,k=18,所以放弃P,Q,使k=18-13-1=4,对R递归地执行本算法;
(6) 将R划分成3(floor(15/5))组:{31,60,33,51,57},{49,35,43,37,52},{32,54,41,46,29}
(7) 求取这3组元素的中值元素分别为:{51,43,41},这个集合的中值元素是43;
(8) 根据43将R划分成3组:

{31, 33, 35,37,32, 41, 29},{43},{60, 51,57, 49, 52,54, 46}

复杂度:

设数组长度为n
当n<75时,算法select所用的计算时间不超过某一常数C1
当n≥75时,for循环执行n/5次,每次用时为某一常数(固定个数即5个中查找!);select找中位数的中位数,由于长度为原长度的1/5,所以用时可记为T(n/5);划分以后所得到数组至多有3n/4个元素,用时记为T(3n/4)。所以T(n)可以递归表示为:

20180504103114678.png

解此递归式为T(n)=O(n)

上述算法将每一组的大小定为5,并选取75作为是否作递归调用的分界点(大于75使用该算法)。这2点保证了T(n)的递归式中2个自变量之和n/5+3n/4=19n/20=εn,0<ε<1。这是使T(n)=O(n)的关键之处。当然,除了5和75之外,还有其他选择。

注意:

(1)设中位数的中位数是x,比x小和比x大的元素至少3*(n-5)/10个,原因:

3*(n/5-1)*1/2

3---中位数比x小的每一组中有3个元素比x小

n/5-1---有5个数的组数

1/2---大概有1/2组的中位数比x小

(2)而当n≥75时,3(n-5)/10≥n/4所以按此基准划分所得的2个子数组的长度都至少缩短1/4,也就是说,长度最长为原长度的3/4。

20180504105639441.png

如图,划分的部分左上是肯定比x小的(大概占1/4)右下是肯定比x大的(大概占1/4)左下和右上不确定,就算这两部分同时不比x小或比x大,划分成的子区间也能至少缩短1/4!

核心代码:

Type Select(Type a[], int p, int r, int k)
{
      if (r-p<75) {
        //用某个简单排序算法对数组a[p:r]排序;
        return a[p+k-1];
        };
      for (int i=0;i<=(r-p-4)/5;i++)//i即为n个元素的分组个数
      //将a[p+5*i]至a[p+5*i+4]的第3小元素与a[p+i]交换位置;
      //将中位数元素换至前面
  
      //找中位数的中位数,r-p-4即上面所说的n-5
      Type x=Select(a,p,p+(r-p-4)/5,(r-p-4)/10);//x是中位数的中位数
      int i=Partition(a,p,r,x),j=i-p+1;//i为快排一趟找到区间[p,r]中x应该在的位置,j为[p,i]区间的元素个数
      if (k<=j) return Select(a,p,i,k);
      else return Select(a,i+1,r,k-j);
}
登录后复制

关键的代码是:

for ( int i = 0; i<=(r-p-4)/5; i++ )//i即为n个元素的分组个数
      //将a[p+5*i]至a[p+5*i+4]的第3小元素与a[p+i]交换位置;
      //将中位数元素换至前面
登录后复制

一共(r-p+1)/5个组

注意这里i从0开始表示,为了方便交换时带入数组的下标,0-(r-p-4)/5,即一共(r-p-4)/5+1各组,即(r-p+1)/5个组

代码如下:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<stack>
#include<algorithm>
using namespace std;

void bubbleSort(int a[],int p,int r){
    for(int i=p;i<r;i++){
        for(int j=i+1;j<=r;j++){
            if(a[j]<a[i])swap(a[i],a[j]);
        }
    }
}

int Partition(int a[],int p,int r,int val){
    int pos;
    for(int q=p;q<=r;q++){
        if(a[q]==val){pos=q;break;}
    }
    swap(a[p],a[pos]);

    int i=p,j=r+1,x=a[p];
    while(1){
        while(a[++i]<x&&i<r);
        while(a[--j]>x);
        if(i>=j)break;
        swap(a[i],a[j]);
    }
    a[p]=a[j];
    a[j]=x;
    return j;
}

int Select(int a[],int p,int r,int k){
    if(r-p<75){
        bubbleSort(a,p,r);
        return a[p+k-1];
    }

    for(int i=0;i<=(r-p-4)/5;i++){//把每个组的中位数交换到区间[p,p+(r-p-4)/4]
        int s=p+5*i,t=s+4;
        for(int j=0;j<3;j++){//冒泡排序,从后开始排,结果使得后三个数是排好顺序的(递增)
            for(int n=s;n<t-j;n++){
                if(a[n]>a[n+1])swap(a[n],a[n-1]);
            }
        }
        swap(a[p+i],a[s+2]);//交换每组中的中位数到前面
    }
    //(r-p-4)/5表示组数-1,则[p,p+(r-p-4)/5]的区间长度等于组数
    int x=Select(a,p,p+(r-p-4)/5,(r-p-4)/10);//求中位数的中位数
    int i=Partition(a,p,r,x),j=i-p+1;
    if(k<=j)return Select(a,p,i,k);
    else return Select(a,i+1,r,k-j);
}
int main(){
    int x;
    //数组a存了0-79
    int a[80]={3,1,7,6,5,9,8,2,0,4,
               13,11,17,16,15,19,18,12,10,14,
               23,21,27,26,25,29,28,22,20,24,
               33,31,37,36,35,39,38,32,30,34,
               43,41,47,46,45,49,48,42,40,44,
               53,51,57,56,55,59,58,52,50,54,
               63,61,67,66,65,69,68,62,60,64,
               73,71,77,76,75,79,78,72,70,74,
              };
    while(scanf("%d",&x)!=EOF){
        printf("第%d大的数是%d\n",x,Select(a,0,79,x));
    }
}
登录后复制

qwq,博主nc写错输出了,“第i小的数”

Snipaste_2019-06-20_11-07-14.png

更多常见问题的相关技术文章,请访问常见问题教程栏目进行学习!

以上是线性时间选择的详细内容。更多信息请关注PHP中文网其他相关文章!

本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

热AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

AI Hentai Generator

AI Hentai Generator

免费生成ai无尽的。

热门文章

R.E.P.O.能量晶体解释及其做什么(黄色晶体)
2 周前 By 尊渡假赌尊渡假赌尊渡假赌
仓库:如何复兴队友
1 个月前 By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island冒险:如何获得巨型种子
1 个月前 By 尊渡假赌尊渡假赌尊渡假赌

热工具

记事本++7.3.1

记事本++7.3.1

好用且免费的代码编辑器

SublimeText3汉化版

SublimeText3汉化版

中文版,非常好用

禅工作室 13.0.1

禅工作室 13.0.1

功能强大的PHP集成开发环境

Dreamweaver CS6

Dreamweaver CS6

视觉化网页开发工具

SublimeText3 Mac版

SublimeText3 Mac版

神级代码编辑软件(SublimeText3)

抖音10级灯牌多少钱?10级粉丝灯牌需要几天? 抖音10级灯牌多少钱?10级粉丝灯牌需要几天? Mar 11, 2024 pm 05:37 PM

在抖音平台上,许多用户都渴望获得等级认证,其中10级灯牌更是展示用户在抖音上的影响力和认可度。本文将深入探讨抖音10级灯牌的价格以及达到这一等级所需的时间,以帮助用户更好地了解这一过程。一、抖音10级灯牌多少钱?抖音10级灯牌的价格会受市场波动和供需情况的影响而有所差异,一般价格在几千元到万元之间。这个价格主要包括灯牌本身的成本和可能的服务费用。用户可以通过抖音官方渠道或第三方服务机构购买10级灯牌,但在购买时要留意选择合法渠道,以免遭遇虚假或欺诈交易。二、10级粉丝灯牌需要几天?达到10级灯牌

linux 可以重置系统时间吗 linux 可以重置系统时间吗 Mar 13, 2023 am 10:50 AM

linux可以重置系统时间,其重置方法是:1、使用date命令查看时间;2、使用“yum install ntp”命令安装ntp;3、通过“ntpdate -u ntp.api.bz”命令实现网络时间同步即可。

为什么我的Go程序需要更长的时间来编译? 为什么我的Go程序需要更长的时间来编译? Jun 09, 2023 pm 06:00 PM

近年来,Go语言已经成为了越来越多开发者的选择。但是,相比其他编程语言而言,Go语言的编译速度却不够快。很多开发者在编译Go程序时都会遇到这样的问题:为什么我的Go程序需要更长时间来编译?本文将会从几个方面探讨这个问题。Go语言的编译器架构Go语言的编译器架构采用的是三阶段设计,分别是前端、中间层和后端。前端负责将源代码翻译成Go语言的中间代码,中间层则将中

小红书发布作品时间怎么设置?发布作品时间准确吗? 小红书发布作品时间怎么设置?发布作品时间准确吗? Mar 24, 2024 pm 01:31 PM

小红书,一个充满生活气息与知识分享的平台,让越来越多的创作者在此畅所欲言。要想在小红书上获得更多的关注和点赞,除了内容质量之外,发布作品的时间也是至关重要的。那么,如何设置小红书发布作品的时间呢?一、小红书发布作品时间怎么设置?1.了解用户活跃时间首先,需要明确小红书用户的活跃时间。通常来说,晚上8点到10点以及周末下午是用户活跃度较高的时段。然而,这个时间段也会受到受众群体和地域等因素的影响而有所不同。因此,为了更好地把握用户活跃时段,建议对不同群体的行为习惯进行更详细的分析。通过了解用户的活

艾尔登法环通关需要多久 艾尔登法环通关需要多久 Mar 11, 2024 pm 12:50 PM

玩家在艾尔登法环中进行游戏时可以体验游戏主线剧情,以及收集游戏成就,有很多玩家不知道艾尔登法环通关需要多久,玩家的通关流程在30个小时。艾尔登法环通关需要多久答:30个小时。1、这个30个小时的通关时长指的虽然不是高手般的速通,但是也省略了很多的流程。2、如果你想获得更好的游戏体验或者是体验完整的剧情,那么时长上肯定要花费更多的时间。3、如果玩家是全收集大约要100-120小时。4、如果是只走主线刷BOSS大约:50-60小时。5、如果是想全部体验:150小时打底。

php 怎么实现时间把时分秒去掉 php 怎么实现时间把时分秒去掉 Mar 13, 2023 am 11:20 AM

php实现时间把时分秒去掉的方法:1、创建一个php示例文件;2、使用strtotime函数将日期时间转换为时间戳;3、通过date函数对日期或时间进行格式化即可去掉时分秒。

Linux 文件时间查看技巧详解 Linux 文件时间查看技巧详解 Feb 21, 2024 pm 01:15 PM

Linux文件时间查看技巧详解在Linux系统中,文件的时间信息对于文件管理和跟踪变更非常重要。Linux系统通过三种主要时间属性来记录文件的变更信息,分别是访问时间(atime)、修改时间(mtime)和更改时间(ctime)。本文将详细介绍如何查看和管理这些文件时间信息,并提供具体的代码示例。1.查看文件时间信息通过使用ls命令结合参数-l可以列出文

如何使用Python中的时间和日期模块 如何使用Python中的时间和日期模块 Oct 16, 2023 am 08:11 AM

如何使用Python中的时间和日期模块导言:在编程中,处理时间和日期是非常常见的任务。Python提供了强大的时间和日期模块,使得处理时间和日期的操作变得更加简单和方便。本文将介绍Python中的时间和日期模块,并提供具体的代码示例,帮助读者更好地理解和应用它们。一、引入时间和日期模块Python内置的时间和日期模块是datetime模块,我们需要先引入该模