【数据结构(邓俊辉)学习笔记】向量04——有序向量

文章目录

  • 0.概述
  • 1.比较器
  • 2.有序性甄别
  • 3.唯一化
    • 3.1低效算法
    • 3.1.1实现
    • 3.1.2 复杂度
    • 3.1.3 改进思路
    • 3.2 高效算法
      • 3.2.1 实现
      • 3.2.2 复杂度
  • 4.查找
    • 4.1统一接口
    • 4.2 语义定义
    • 4.3 二分查找
      • 4.3.1 原理
      • 4.3.2 实现
      • 4.3.3 复杂度
      • 4.3.4 查找长度
      • 4.3.5 不足
    • 4.4 Fibonacci查找
      • 4.4.1 改进思路
      • 4.4.2 黄金分割
      • 4.4.3 实现
      • 4.4.4 复杂度分析
      • 4.4.5 平均查找长度
    • 4.5 通用策略
    • 4.6 结论

0.概述

若向量S[0, n)中的所有元素不仅按线性次序存放,而且其数值大小也按此次序单调分布,则称作有序向量(sorted vector)。

1.比较器

有序向量的定义的先决条件:各元素之间必须能够比较大小和判等操作。这一条件构成了有序向量中“次序”概念的基础,否则所谓的“有序”将无从谈起。

复杂数据对象应重载"<“和”<="等操作符。

2.有序性甄别

在这里插入图片描述
算法思想:顺序扫描整个向量,逐一比较每一对相邻元素——向量已经有序,当且仅当它们都是顺序的。

template <typename T> 
int Vector<T>::disordered() const { //返回向量中逆序相邻元素对的总数int n = 0; //计数器for ( int i = 1; i < _size; i++ ) //逐一检查_size - 1对相邻元素if ( _elem[i - 1] > _elem[i] ) n++; //逆序则计数return n; //向量有序当且仅当n = 0
}

3.唯一化

出于效率的考虑,为清除无序向量中的重复元素,一般做法往往是首先将其转化为有序向量

3.1低效算法

3.1.1实现

算法思想:
在这里插入图片描述

template <typename T> 
int Vector<T>::uniquify() { //有序向量重复元素剔除算法(低效版)int oldSize = _size; int i = 1; //当前比对元素的秩,起始于首元素while ( i < _size ) //从前向后,逐一比对各对相邻元素_elem[i - 1] == _elem[i] ? remove ( i ) : i++; //若雷同,则初除后者;否则,转至后一元素return oldSize - _size; //向量规模发化量,即被初除元素总数
}

3.1.2 复杂度

在这里插入图片描述
分析需用结论:remove()操作的复杂度线性正比于被删除元素的后继元素总数。不清除的可看无序向量。

最坏情况下:
当所有元素均雷同时,用于所有这些remove()操作的时间总量将高达:
(n - 2) + (n - 3) + … + 2 + 1= O( n 2 n^2 n2) 由算术级数得 。不清楚可看算法分析

这一效率竟与向量未排序时相同,说明该方法未能充分利用此时向量的有序性。

3.1.3 改进思路

反思:低效的根源在于,同一元素可作为被删除元素的后继多次前移
启示:若能以重复区间为单位,成批删除雷同元素,性能必能改进。

3.2 高效算法

3.2.1 实现

算法思想:
可以区间为单位成批地删除前后紧邻的各组重复元素,并将其后继元素(若存在)统一地大跨度前移。

template <typename T> 
Rank Vector<T>::uniquify() { //有序向量重复元素剔除算法(高效版)Rank i = 0, j = 0; //各对互异“相邻”元素的秩while ( ++j < _size ) //逐一扫描,直至末元素if ( _elem[i] != _elem[j] ) //跳过雷同者_elem[++i] = _elem[j]; //发现不同元素时,向前移至紧邻于前者右侧_size = ++i; shrink(); //直接截除尾部多余元素return j - i; //向量规模变化量,即被删除元素总数
}

3.2.2 复杂度

在这里插入图片描述
由此可知,uniquify()算法的时间复杂度应为O(n),较之无序向量唯一化算法的O( n 2 n^2 n2),效率整整提高了一个线性因子。关键在于向量已经排序

4.查找

4.1统一接口

为区别于无序向量的查找接口find(),有序向量的查找接口将统一命名为search()。外部接口形式上统一,内部实现算法却不见得完全统一。

template <typename T> //在有序向量的区间[lo, hi)内,确定不大于e的最后一个节点的秩
Rank Vector<T>::search( T const& e, Rank lo, Rank hi ) const { // 0 <= lo < hi <= _sizereturn ( rand() % 2 ) ? binSearch( _elem, e, lo, hi ) : fibSearch( _elem, e, lo, hi );
} //等概率地随机使用二分查找、Fibonacci查找
  • 如何处理特殊情况?
    比如,目标不存在;或者反过来,目标元素同时存在多个

4.2 语义定义

在语义上进一步的细致约定,使search()接口作为一个基本部件为其他算法利用。

在有序向量区间V[lo,hi)中,确定不大于e的最后一个元素。
在这里插入图片描述

4.3 二分查找

4.3.1 原理

在这里插入图片描述
每经过至多两次比较操作,可以将查找问题简化为一个规模更小的新问题。如此,借助递归机制即可便捷地描述和实现此类算法。

4.3.2 实现

算法思想:减而治之

// 二分查找算法(版本A):在有序向量的区间[lo, hi)内查找元素e,0 <= lo <= hi <= _size
template <typename T> 
static Rank binSearch ( T* A, T const& e, Rank lo, Rank hi ) {while ( lo < hi ) { //每步迭代可能要做两次比较判断,有三个分支Rank mi = ( lo + hi ) >> 1; //以中点为轴点if ( e < A[mi] ) hi = mi; //深入前半段[lo, mi)继续查找else if ( A[mi] < e ) lo = mi + 1; //深入后半段(mi, hi)继续查找else return mi; //在mi处命中} //成功查找可以提前终止return -1; //查找失败
} //有多个命中元素时,不能保证返回秩最大者;查找失败时,简单地迒回-1,而且能指示失败的位置
  • 通过快捷的整数移位操作回避了相对更加耗时的除法运算。
  • 通过引入lo、hi和mi等变量,将减治算法通常的递归模式改成了迭代模式。(递归消除)

4.3.3 复杂度

在这里插入图片描述
随着迭代的不断深入,有效的查找区间宽度将按1/2的比例以几何级数的速度递减。经过至多log2(hi - lo)步迭代后,算法必然终止。故总体时间复杂度不超过:
O( l o g 2 ( h i − l o ) log_2(hi - lo) log2(hilo)) = O(logn)
上图中的递归公式也可得出这个结论,递推公式不熟悉的可以看递推分析。

顺序查找算法的O(n)复杂度相比无序向量的查找find()无序向量,O(logn)几乎改进了一个线性因子(任意c > 0,logn = O( n c n^c nc))。

4.3.4 查找长度

查找算法的整体效率主要地取决于其中所执行的元素大小比较操作的次数,即所谓查找长度。

通常,需分别针对成功与失败查找,从最好、最坏、平均等角度评估

结论:此版二分查找成功、失败时的平均查找长度均大致为O(1.5logn)

4.3.5 不足

尽管二分查找算法(版本A)即便在最坏情况下也可保证O(logn)的渐进时间复杂度,但就其常系数1.5而言仍有改进余地。

4.4 Fibonacci查找

4.4.1 改进思路

在这里插入图片描述
解决问题的思路:

  1. 调整前、后区域的宽度,适当地加长(缩短)前(后)子向量
  2. 统一沿两个方向深入所需要执行的比较次数,比如都统一为一次

4.4.2 黄金分割

实际上,减治策略本身并不要求子向量切分点mi必须居中,故按上述改进思路,不妨按黄金分割比来确定mi。
在这里插入图片描述

4.4.3 实现

算法思路:减治策略——黄金分割比来确定mi

#include "..\fibonacci\Fib.h" //引入Fib数列类
// Fibonacci查找算法(版本A):在有序向量的区间[lo, hi)内查找元素e,0 <= lo <= hi <= _size
template <typename T> 
static Rank fibSearch ( T* A, T const& e, Rank lo, Rank hi ) {Fib fib ( hi - lo ); //用O(log_phi(n = hi - lo)时间创建Fib数列while ( lo < hi ) { //每步迭代可能要做两次比较判断,有三个分支while ( hi - lo < fib.get() ) fib.prev(); //通过向前顺序查找(分摊O(1))——至多迭代几次?Rank mi = lo + fib.get() - 1; //确定形如Fib(k) - 1的轴点if ( e < A[mi] ) hi = mi; //深入前半段[lo, mi)继续查找else if ( A[mi] < e ) lo = mi + 1; //深入后半段(mi, hi)继续查找else  return mi; //在mi处命中} //成功查找可以提前终止return -1; //查找失败
} //有多个命中元素时,不能保证返回秩最大者;失败时,简单地迒回-1,而且能指示失败的位置

对Fib数不清楚得可以看算法设计优化——Fibonacci数

4.4.4 复杂度分析

进入循环之前调用构造器Fib(n = hi - lo),将初始长度设置为“不小于n的最小Fibonacci项”。这一步所需花费的O( l o g ϕ log_\phi logϕn)时间,分摊到后续O( l o g ϕ log_\phi logϕn)步迭代中,并不影响算法整体的渐进复杂度。

4.4.5 平均查找长度

结论:O(1.44∙log2n)

4.5 通用策略

在这里插入图片描述

4.6 结论

  • 二分查找算法的时间复杂度O(logn),平均查找长度O(1.5∙log2n)
  • Fibonacci查找算法的时间复杂度O(logn),平均查找长度O(1.44∙log2n)

Fibonacci查找算法效率略有提高。

二分查找和Fibonacci查找接口均为严格符合search()接口语义,即返回确定不大于e的最后一个元素得秩,而不是-1。还可改进见有序向量二分查找算法与Fibonacci查找算法

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/317373.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

图搜索算法详解与示例代码

在计算机科学领域&#xff0c;图搜索算法是一类用于在图数据结构中查找特定节点或路径的算法。图搜索算法在许多领域都有着广泛的应用&#xff0c;包括网络路由、社交网络分析、游戏开发等。本文将详细介绍几种常见的图搜索算法&#xff0c;包括深度优先搜索&#xff08;DFS&am…

视频改字祝福 豪车装X系统源码uniapp前端源码

内容目录 一、详细介绍二、效果展示1.部分代码2.效果图展示 三、学习资料下载 一、详细介绍 uniapp视频改字祝福 豪车装X系统源码 全开源。 创意无限&#xff01;AI视频改字祝福&#xff0c;豪车装X系统源码开源&#xff0c;打造个性化祝福视频不再难&#xff01; 想要为你的…

【论文阅读】ChipNeMo中的数据集处理

前面总体学习了《ChipNeMo: Domain-Adapted LLMs for Chip Design》&#xff0c;然后又继续仔细看了论文中的领域适配分词和领域数据微调的预训练检索模型&#xff0c;对于数据集的处理&#xff0c;也需要仔细看一下。 提炼重点&#xff1a;1&#xff09;对于数据集&#xff0…

Docker: 如何不新建容器 修改运行容器的端口

目录 一、修改容器的映射端口 二、解决方案 三、方案 一、修改容器的映射端口 项目需求修改容器的映射端口 二、解决方案 停止需要修改的容器 修改hostconfig.json文件 重启docker 服务 启动修改容器 三、方案 目前正在运行的容器 宿主机的3000 端口 映射 容器…

启发式搜索算法4 -遗传算法实战:吊死鬼游戏

相关文章: 启发式搜索算法1 – 最佳优先搜索算法 启发式搜索算法2 – A*算法 启发式搜索算法2 – 遗传算法 有一个小游戏叫吊死鬼游戏&#xff08;hangman&#xff09;&#xff0c;在学习英语的时候&#xff0c;大家有可能在课堂上玩过。老师给定一个英文单词&#xff0c;同学们…

设计模式之监听器模式ListenerPattern(三)

一、介绍 监听器模式是一种软件设计模式&#xff0c;在对象的状态发生改变时&#xff0c;允许依赖它的其他对象获得通知。在Java中&#xff0c;可以使用接口和回调机制来实现监听器模式。 二、代码实例 1、事件Event类 package com.xu.demo.listener;// 事件类 public class…

Python 与 TensorFlow2 生成式 AI(三)

原文&#xff1a;zh.annas-archive.org/md5/d06d282ea0d9c23c57f0ce31225acf76 译者&#xff1a;飞龙 协议&#xff1a;CC BY-NC-SA 4.0 第七章&#xff1a;使用 GAN 进行风格转移 神经网络在涉及分析和语言技能的各种任务中正在取得进步。创造力是人类一直占有优势的领域&…

深入浅出TCP 与 UDP

&#x1f525; 引言 在互联网的广阔天地里&#xff0c;TCP&#xff08;Transmission Control Protocol&#xff09;和UDP&#xff08;User Datagram Protocol&#xff09;作为传输层的两大支柱&#xff0c;各自承担着不同的使命。下面这篇文章将带你从基础到进阶&#xff0c;全…

如何安全可控的进行跨区域数据交换,提高数据价值?

跨区域数据交换指的是在不同地理位置或不同网络环境下的数据传输和共享。随着数字化转型的加速&#xff0c;企业及组织越来越依赖于数据的流动来优化业务流程、增强决策制定和推动创新。然而&#xff0c;跨区域数据交换也带来了一系列的挑战和风险&#xff0c;主要包括&#xf…

天地图路径规划功能实现

目录 1、天地图路径规划2、路径规划3、参数说明4、Demo 1、天地图路径规划 天地图Web服务API为用户提供HTTP/HTTPS接口&#xff0c;即开发者可以通过这些接口使用各类型的地理信息数据服务&#xff0c;可以基于此开发跨平台的地理信息应用。 Web服务API对所有用户开放。使用本…

分享天某云对象存储开发的体验

最近体验了天某云对象存储的功能&#xff0c;作为一名资深开发者&#xff0c;开发体验差强人意&#xff0c;与阿里云存在一定的差距。 首先在开发文档上居然没有基于nodejs的代码示例&#xff0c;只有java,c#,go等的代码示例&#xff0c;虽然有javascript的&#xff0c;但那也只…

正点原子[第二期]Linux之ARM(MX6U)裸机篇学习笔记-5

前言&#xff1a; 本文是根据哔哩哔哩网站上“正点原子[第二期]Linux之ARM&#xff08;MX6U&#xff09;裸机篇”视频的学习笔记&#xff0c;在这里会记录下正点原子 I.MX6ULL 开发板的配套视频教程所作的实验和学习笔记内容。本文大量引用了正点原子教学视频和链接中的内容。…

计算机视觉——OpenCV 使用分水岭算法进行图像分割

分水岭算法 分水岭算法&#xff1a;模拟地理形态的图像分割 分水岭算法通过模拟自然地形来实现图像中物体的分类。在这一过程中&#xff0c;每个像素的灰度值被视作其高度&#xff0c;灰度值较高的像素形成山脊&#xff0c;即分水岭&#xff0c;而二值化阈值则相当于水平面&am…

Windows如何通过wsl2迅速启动Docker desktop的PHP的Hyperf项目容器?

一、安装WSL 什么是WSL&#xff1f; 官网&#xff1a;什么是WSL&#xff1f; Windows Subsystem for Linux (WSL) 是一个在Windows 10和Windows 11上运行原生Linux二进制可执行文件的兼容性层。 换句话说&#xff0c;WSL让你可以在Windows系统上运行Linux环境&#xff0c;而无需…

【Web】2024XYCTF题解(全)

目录 ezhttp ezmd5 warm up ezMake ez?Make εZ?мKε? 我是一个复读机 牢牢记住&#xff0c;逝者为大 ezRCE ezPOP ezSerialize ezClass pharme 连连看到底是连连什么看 ezLFI login give me flag baby_unserialize ezhttp 访问./robots.txt 继…

linux高性能服务器--Ngix内存池简单实现

文章目录 内存模型&#xff1a;流程图内存对齐code 内存模型&#xff1a; 流程图 内存对齐 对齐计算 要分配一个以指定大小对齐的内存&#xff0c;可以使用如下公式&#xff1a; 假设要分配大小为n&#xff0c;对齐方式为x&#xff0c;那么 size(n(x-1)) & (~(x-1))。 举个…

【分布式通信】NPKit,NCCL的Profiling工具

NPKit介绍 NPKit (Networking Profiling Kit) is a profiling framework designed for popular collective communication libraries (CCLs), including Microsoft MSCCL, NVIDIA NCCL and AMD RCCL. It enables users to insert customized profiling events into different C…

26.统一网关Gateway

网关的功能 1.身份认证&#xff0c;权限的校验。 2.服务的路由&#xff0c;负载均衡。用户请求被分配到哪一个微服务。一个微服务可以有多个实例&#xff0c;所以使用负载均衡。 3.请求限流。 springcloud网关实现有两种&#xff1a;gateway, zuul zuul是基于servlet实现的…

随笔Ubuntu上的的一些使用

Ubuntu简易使用 常用指令 cdlsmkdirrf -rm 路径 换源 备份镜像 sudo cp /etc/apt/sources.list /etc/apt/sources.list.bak编辑文件设置 sudo gedit /etc/apt/sources.list清华源 # 阿里源 deb http://mirrors.aliyun.com/ubuntu/ bionic main restricted universe mul…

数据仓库Data Warehouse

数据仓库Data Warehouse 数仓是一种思想,数仓是一种规范,数仓是一种解决方案 1. 数据处理方式 数据处理大致可以分成两大类: 联机事务处理OLTP(on-line transaction processing)联机分析处理OLAP(On-Line Analytical Processing)1.1. OLTP OLTP的全称是On-line Transa…