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

【算法设计与分析qwl】伪码——顺序检索,插入排序

伪代码:

 例子:

改进的顺序检索 Search(L,x)
输入:数组L[1...n],元素从小到大排序,数x
输出:若x在L中,输出x位置下标 j ,否则输出0

j <- 1

while j<=n and x>L[j] do j <- j+1

if x<L[j]  or j >n then j<- 0

return j

插入排序

插入排序 Insert Sort(A,n)
输入:n个元素的数组A
输出:按照递增顺序排好序的数组A

for j <- 2 to n do //从第2到第n个数进行插入

        x <- A[j]

        i <- j-1 //3-7行把A[j]插入A[1..j-1]

        while i>0 and x<A[i]  do 

                A[i+1] <- A[i]

                i <- i-1

        A[i+1] <- x


 

 

顺序检索:

 例子:检索

顺序检索算法:

 实例:

最坏情况的时间估计: 

 

 在数组中或位于间隙处。

 平均情况的时间估计:

假设x在L中概率是p , 且每个位置概率相等。

 如果在数列里:p/n是在第i个位置的概率,第i个位置需要比较i次。对n个位置进行求和。

如果不在数列里:出现概率是(1-p) 每种情况都是n次比较。

 

 改进顺序检索算法:

 不在数组中时:比较到 x1<x<x2时就结束比较。

改进的顺序检索 Search(L,x)
输入:数组L[1...n],元素从小到大排序,数x
输出:若x在L中,输出x位置下标 j ,否则输出0

j <- 1

while j<=n and x>L[j] do j <- j+1

if x<L[j]  or j >n then j<- 0

return j

 时间估计:
最坏情况:W(n)=n

 平均情况:

输入实例的概率分布:假设x在L中每个位置与空隙的概率都相等。
可能是:sum i =1 to n:(i * p/n ) + sum i=1 to n+1 ( i *(1-p)/(n+1) )

相关文章:

【算法设计与分析qwl】伪码——顺序检索,插入排序

伪代码&#xff1a; 例子&#xff1a; 改进的顺序检索 Search(L,x)输入&#xff1a;数组L[1...n]&#xff0c;元素从小到大排序&#xff0c;数x输出&#xff1a;若x在L中&#xff0c;输出x位置下标 j ,否则输出0 j <- 1 while j<n and x>L[j] do j <- j1 if x<…...

Uniapp路由拦截-自定义路由白名单

步骤一:新建routerIntercept.js文件 步骤二:routerIntercept文件中写入:(根据自己需要修改whiteList白名单中的页面路径和自己的逻辑处理) import Vue from vue // 白名单 const whiteList = [/pages/public/login,/pages/public/privacyAgreement, ]export default asy…...

在中国可以使用 HubSpot 吗?

当谈到市场营销和客户关系管理工具时&#xff0c;HubSpot通常是一家企业的首选。然而&#xff0c;对于许多中国的企业来说&#xff0c;一个重要的问题是&#xff1a;在中国可以使用HubSpot吗&#xff1f;这个问题涉及到不同的方面&#xff0c;包括政策法规、社交媒体平台、语言…...

Java的基础应用

Java是一种广泛应用于软件开发的编程语言&#xff0c;基础应用涵盖了很多方面。以下是Java的一些基础应用方面的介绍&#xff1a; 1. 控制流语句&#xff1a;Java中的程序流程控制语句分为选择语句和循环语句。选择语句包括if-else语句和switch语句&#xff0c;循环语句包括fo…...

【excel】列转行

列转行 工作中有一些数据是列表&#xff0c;现在需要转行 选表格内容&#xff1a;在excel表格中选中表格数据区域。点击复制&#xff1a;在选中表格区域处右击点击复制。点击选择性粘贴&#xff1a;在表格中鼠标右击点击选择性粘贴。勾选转置&#xff1a;在选择性粘勾选转置选…...

用Bing绘制「V我50」漫画;GPT-5业内交流笔记;LLM大佬的跳槽建议;Stable Diffusion生态全盘点第一课 | ShowMeAI日报

&#x1f440;日报&周刊合集 | &#x1f3a1;生产力工具与行业应用大全 | &#x1f9e1; 点赞关注评论拜托啦&#xff01; &#x1f525; 美国升级AI芯片出口禁令&#xff0c;13家中国GPU企业被列入实体清单 nytimes.com/2023/10/05/technology/chip-makers-china-lobbying…...

Java身份证实名认证-阿里云API 【姓名、身份证号】

1. 阿里云API市场 https://market.aliyun.com/products/57126001/cmapi00053442.html?spm5176.2020520132.101.3.a6217218nxxEiy#skuyuncode47442000022 购买对应套餐 2. 复制AppCode https://market.console.aliyun.com/imageconsole/index.htm#/?_kl85e10 云市场-已购买服…...

ND协议——无状态地址自动配置 (SLAAC)

参考学习&#xff1a;计算机网络 | 思科网络 | 无状态地址自动配置 (SLAAC) | 什么是SLAAC_瘦弱的皮卡丘的博客-CSDN博客 与 IPv4 类似&#xff0c;可以手动或动态配置 IPv6 全局单播地址。但是&#xff0c;动态分配 IPv6 全局单播地址有两种方法&#xff1a; 如图所示&#…...

iOS开发UITableView的使用,区别Plain模式和Grouped模式

简单赘述一下 的创建步骤 // 创建UITableView self.tableView [[UITableView alloc] initWithFrame:self.view.bounds style:UITableViewStylePlain]; // 设置数据源和代理 self.tableView.dataSource self; self.tableView.delegate self; // 注册自定义UITableViewCe…...

css美化滚动条

/*定义滚动条高宽及背景 高宽分别对应横竖滚动条的尺寸*/ ::-webkit-scrollbar { width: 8px; height: 8px; background-color: rgba(0,0,0,.2); } /*定义滚动条轨道 内阴影圆角*/ ::-webkit-scrollbar-track { -webkit-box…...

【CANoe】XML Test Module使用实例

文章目录 一、实操步骤1、增加XML Test Module节点2、配置XML Test Module节点3、XML Test Module节点增加CAPL脚本(.can文件)4、文件夹结构5、使用仿真节点开始测试6、测试结果与测试报告7、同理&#xff0c;在Test Setup也可如此操作 一、实操步骤 1、增加XML Test Module节…...

oracle的update语句where条件后的索引字段为空时不执行

问题描述&#xff1a; update 表名 set age ‘23’ where id1 and name‘lili’; 当在oracle执行以上sql时执行成功&#xff0c;但是当传入的name为null时&#xff0c;sql不成立。我的表中id和name是联合唯一索引&#xff0c;以为name不会为空&#xff0c;但实际上name可以为空…...

RabbitMQ的特点

RabbitMQ是一个开源的消息中间件&#xff0c;用于在不同的应用程序之间进行异步通信。它支持多种消息传递协议&#xff0c;如AMQP、MQTT、STOMP等。 RabbitMQ具有以下特点&#xff1a; 可扩展性&#xff1a;RabbitMQ可以通过添加更多的节点和队列来实现水平扩展。 可靠性&…...

JS单选框默认选中样式修改,为白色背景中心有黑色小圆点的样式

要修改JavaScript中默认选中的单选框的样式为白色背景并带有黑色小圆点&#xff0c;你可以使用CSS来实现。以下是一个示例&#xff0c;展示如何修改样式&#xff1a; <style>/* 修改默认选中单选框的样式 */input[type"radio"]:checked {appearance: none; /*…...

2023年下半年NPDP考试今天开始报名!

2023年第二次NPDP考试将于2023年12月2日&#xff08;周六&#xff09;举行&#xff0c;考试报名相关事项安排如下&#xff1a; 一、考试时间&#xff1a; 12月2日09:00-12:30。 二、报名时间&#xff1a; 10月18日08:00-11月10日23:59。 三、缴费及退考截止时间&#xff1…...

nfs+rpcbind实现服务器之间的文件共享

NFS简介 NFS服务及Network File System&#xff0c;用于在网络上共享存储&#xff0c;分为2,3,4三个版本&#xff0c;最新为4.1版本。NFS基于RPC协议&#xff0c;RPC为Remote Procedure Call的简写。 应用场景&#xff1a;用于A,B,C三台机器上需要保证被访问到的文件是一样…...

10-k8s-身份认证与鉴权

文章目录 一、ServiceAccount介绍二、ServiceAccount相关的资源对象三、dashboard空间示例 一、ServiceAccount介绍 ServiceAccount&#xff08;服务账户&#xff09;概念介绍 1&#xff09;ServiceAccount是Kubernetes集群中的一种资源对象&#xff0c;用于为Pod或其他资源提供…...

如何分析K8S中的OOMKilled问题(Exit Code 137)

什么是 OOMKilled Kubernetes 错误&#xff08;Exit Code 137&#xff09; 当 Kubernetes 集群中的容器超过其内存限制时&#xff0c;Kubernetes 系统可能会终止该容器并显示“OOMKilled”错误&#xff0c;这表明该进程由于内存不足而被终止。此错误的退出代码是 137。 如果遇…...

【0day】泛微e-office OA未授权访问漏洞学习

注:该文章来自作者日常学习笔记,请勿利用文章内的相关技术从事非法测试,如因此产生的一切不良后果与作者无关。 目录 一、漏洞描述 二、影响版本 三、资产测绘 四、漏洞复现...

CSS盒子模型的详细解析

03-盒子模型 作用&#xff1a;布局网页&#xff0c;摆放盒子和内容。 盒子模型-组成 内容区域 – width & height 内边距 – padding&#xff08;出现在内容与盒子边缘之间&#xff09; 边框线 – border 外边距 – margin&#xff08;出现在盒子外面&#xff09; d…...

7.4.分块查找

一.分块查找的算法思想&#xff1a; 1.实例&#xff1a; 以上述图片的顺序表为例&#xff0c; 该顺序表的数据元素从整体来看是乱序的&#xff0c;但如果把这些数据元素分成一块一块的小区间&#xff0c; 第一个区间[0,1]索引上的数据元素都是小于等于10的&#xff0c; 第二…...

Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误

HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误&#xff0c;它们的含义、原因和解决方法都有显著区别。以下是详细对比&#xff1a; 1. HTTP 406 (Not Acceptable) 含义&#xff1a; 客户端请求的内容类型与服务器支持的内容类型不匹…...

1.3 VSCode安装与环境配置

进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件&#xff0c;然后打开终端&#xff0c;进入下载文件夹&#xff0c;键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...

零基础设计模式——行为型模式 - 责任链模式

第四部分&#xff1a;行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习&#xff01;行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想&#xff1a;使多个对象都有机会处…...

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别 直接训练提示词嵌入向量的核心区别 您提到的代码: prompt_embedding = initial_embedding.clone().requires_grad_(True) optimizer = torch.optim.Adam([prompt_embedding...

pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)

目录 一、SQL注入 二、insert注入 三、报错型注入 四、updatexml函数 五、源码审计 六、insert渗透实战 1、渗透准备 2、获取数据库名database 3、获取表名table 4、获取列名column 5、获取字段 本系列为通过《pikachu靶场通关笔记》的SQL注入关卡(共10关&#xff0…...

今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存

文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...

重启Eureka集群中的节点,对已经注册的服务有什么影响

先看答案&#xff0c;如果正确地操作&#xff0c;重启Eureka集群中的节点&#xff0c;对已经注册的服务影响非常小&#xff0c;甚至可以做到无感知。 但如果操作不当&#xff0c;可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...

【Linux系统】Linux环境变量:系统配置的隐形指挥官

。# Linux系列 文章目录 前言一、环境变量的概念二、常见的环境变量三、环境变量特点及其相关指令3.1 环境变量的全局性3.2、环境变量的生命周期 四、环境变量的组织方式五、C语言对环境变量的操作5.1 设置环境变量&#xff1a;setenv5.2 删除环境变量:unsetenv5.3 遍历所有环境…...

日常一水C

多态 言简意赅&#xff1a;就是一个对象面对同一事件时做出的不同反应 而之前的继承中说过&#xff0c;当子类和父类的函数名相同时&#xff0c;会隐藏父类的同名函数转而调用子类的同名函数&#xff0c;如果要调用父类的同名函数&#xff0c;那么就需要对父类进行引用&#…...