【21天算法学习】索引查找

简介: 【21天算法学习】索引查找

作者简介:

🍀姓姜,字君竹。

🍁浅薄观点:科以载文,文以载道

🌱软件技术升计科,计划考研

🌾要有最朴素的生活和最遥远的梦想,即使明日,天寒地冻,路遥马亡


1.概念及介绍

 索引查找主要氛围基本索引查找和分块查找,核心思想是对于无序的数据集合,先建立所以表,是的索引表有序和或分块有序,结合顺序查找与索引查找的方法完成查找。

 基本索引查找是基于一个有序的索引表进行折半查找,然后再根据索引表与主数据表的关系确定数据所在位置的过程。所以只需要在折半查找后,从索引中取出该元素在主数据集合中对应的位置即可。

 使用分块查找时,主数据表必须满足该规律:按一定的区间长度进行分块后,前一块中的最大关键字小于后一块中的最小值,即后一块中的任意元素都大于前一块中的所有元素,关键字存储的就是这一块中足底啊的关键字的值。

在进行分块查找时易燃是先在索引表上进行折半查找,确定待查元素所在分块。由于分块内部的元素无序,所以分块内部(基于快索引表的快区间端点)再食用顺序查找确定元素的最终位置。


2.时间空间复杂度

2.1 基本索引查找:

 对于完整的索引查找,整个过程包含索引的建立和元素的查找两个步骤。对于索引表的建立可以使用不同的排序算法时效内,有可能有多种情况。索引表是一个有序的集合,先在此基础上进行折半查找,然后根据索引表中存储的信息提取出对应的位置,此处为常数级O(1)。所以对于查找部分,时间复杂度与折半查找为通过一下级别:O(log2n)。

 对于基本索引表,相当于是对主数据进行排序后完整的存储下来,因此除去一些临时变量外,主要需要对索引表分配额外的存储空间,与输入数据的量级相同:O(n)。

2.2 分块查找:

 对于分块查找,需要主数据表本身满足一定的规律,在此之上只需要指定一个合理的区间长度,就可以得到一个分块索引表,主要的消耗在于存储,所以分块查找可以看做是两次查找:分块的折半查找和分块内的顺序查找。时间复杂度不会超过O(n)。

 由于选定的区间长度不唯一,所以需要的存储空间也不确定,一班为n/a,a为常数,最多也不会超过O(n)。


3.图解

3.1 基本索引查找:

3.2 分块查找:

4. 代码实现

4.1 基本索引查找:

4.2分块查找:


又停电了,之后再补,烦死了。


学习的最大理由是想摆脱平庸,早一天就多一份人生的精彩;迟一天就多一天平庸的困扰。


目录
相关文章
|
3月前
|
存储 算法
数据结构与算法学习二二:图的学习、图的概念、图的深度和广度优先遍历
这篇文章详细介绍了图的概念、表示方式以及深度优先遍历和广度优先遍历的算法实现。
74 1
数据结构与算法学习二二:图的学习、图的概念、图的深度和广度优先遍历
|
2月前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
数据结构与算法系列学习之串的定义和基本操作、串的储存结构、基本操作的实现、朴素模式匹配算法、KMP算法等代码举例及图解说明;【含常见的报错问题及其对应的解决方法】你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
|
2月前
|
机器学习/深度学习 人工智能 自然语言处理
【EMNLP2024】基于多轮课程学习的大语言模型蒸馏算法 TAPIR
阿里云人工智能平台 PAI 与复旦大学王鹏教授团队合作,在自然语言处理顶级会议 EMNLP 2024 上发表论文《Distilling Instruction-following Abilities of Large Language Models with Task-aware Curriculum Planning》。
|
3月前
|
缓存 算法 Java
JVM知识体系学习六:JVM垃圾是什么、GC常用垃圾清除算法、堆内存逻辑分区、栈上分配、对象何时进入老年代、有关老年代新生代的两个问题、常见的垃圾回收器、CMS
这篇文章详细介绍了Java虚拟机(JVM)中的垃圾回收机制,包括垃圾的定义、垃圾回收算法、堆内存的逻辑分区、对象的内存分配和回收过程,以及不同垃圾回收器的工作原理和参数设置。
113 4
JVM知识体系学习六:JVM垃圾是什么、GC常用垃圾清除算法、堆内存逻辑分区、栈上分配、对象何时进入老年代、有关老年代新生代的两个问题、常见的垃圾回收器、CMS
|
3月前
|
算法
动态规划算法学习三:0-1背包问题
这篇文章是关于0-1背包问题的动态规划算法详解,包括问题描述、解决步骤、最优子结构性质、状态表示和递推方程、算法设计与分析、计算最优值、算法实现以及对算法缺点的思考。
131 2
动态规划算法学习三:0-1背包问题
|
2月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习(8)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
2月前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之顺序表【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找等具体详解步骤以及举例说明
|
2月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
2月前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构之单双链表按位、值查找;[前后]插入;删除指定节点;求表长、静态链表等代码及具体思路详解步骤;举例说明、注意点及常见报错问题所对应的解决方法
|
2月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
下一篇
开通oss服务