djesue 2022-04-29 10:56
浏览 8
已结题

分块查找中，有序元素n个在索引表和分块中都用折半查找最好分块为什么是sqrt(n)

问题遇到的现象和发生背景

在23王道书上的一道课后习题如下：

img


在书上只是说了索引表用顺序查找分块为sqrt(n)最好，为什么折半也是sqrt(n)呢

img

我想要达到的结果

希望可以用数学公式来说明下

  • 写回答

0条回答 默认 最新

    报告相同问题？

    • 408数据结构-折半查找，分块查找 自学知识点整理
      2024-10-20 20:23
      浮游大陆群的旅人的博客 （下图来自王道考研408数据结构课程视频的截图 - 折半查找） 若有序序列有 n n n个元素，则对应的判定树有 n n n个圆形的非叶结点和 n + 1 n+1 n+1个方形的叶结点。因此，判定树是一棵平衡二叉树。（后续博客会写）...
    • 线性索引查找产生以及三种线性索引方式（稠密索引、分块索引和倒排索引）
      2024-02-02 13:57
      Kegi_的博客 稠密索引是指在线性索引中，将数据集中的每个记录对应一个索引项，小例子和稠密索引还是略有不同，家里的东西毕竟少，小本子再多也就几十页，全部翻看完就几分钟时间，而稠密索引要应对的可能是成千上万的数据，因此...
    • 【数据结构】第七章：查找
      2025-03-16 20:42
      iFulling的博客 【数据结构】第七章：查找 一、基本概念 1. 概念 2. 查找算法的效率评价 二、顺序查找 1. 算法思想 2. 算法实现 3. 算法优化 三、折半查找 1. 算法思想 2. 算法实现 3. 查找判定树 4. 折半查找效率 四、分块查找 1. ...
    • 考研408笔记之数据结构（六）——查找
      2025-01-20 19:03
      苦 涩的博客 平衡二叉树，简称平衡树（AVL树）――树上任一结点的左子树和右子树的高度之差不超过1。在平衡二叉树里，每个结点都有一个平衡因子，结点的平衡因子=左子树高-右子树高。根据平衡二叉树定义可以知道平衡因子只能取1...
    • 数据结构——查找（c）
      2021-12-10 15:49
      阿笙_1202的博客 分块查找(索引顺序查找)三、动态查找表1.二叉排序树2.平衡二叉树3.B-树4.B+树5.B-树和B+树四、哈希表（散列表）1.基本概念2.散列函数的构造方法3. 解决冲突的方法⚝4.散列查找的性能分析5.散列（哈希）查找过程 一...
    • 【数据结构笔记】6.查找
      2021-04-14 15:27
      江城暮的博客 其逻辑结构和线性表非常相似，其逻辑结构的区别仅在于串的数据对象限定为字符集。空串：字符的个数为0的串称为空串。子串：串中任意个连续的字符组成的子序列称为该串的子串。主串：包含子串的串称为主串。子串的...
    • 数据结构笔记（王道考研） 第七章：查找
      2022-08-12 22:10
      CS_Lee_的博客 数据结构笔记（王道考研） 第七章：查找
    • 各种查找算法的效率分析
      2023-08-09 21:29
      rebekk的博客 + n + n n + 1 = n 2 + n n + 1 \frac{1+2+...+n+n}{n+1}=\frac{n}{2}+\frac{n}{n+1} n+11+2+...+n+n​=2n​+n+1n​ 折半查找（二分查找） 用折半查找法找到给定值的比较次数不会超过树的高度（n个元素的树高为 ⌈ ...
    • 三大经典查找（跳跃、插值、斐波那契）
      2022-07-05 11:43
      小白还在写代码的博客 查找和排序是数据结构与算法中不可或缺的一环，在这个专栏中我们会学习六大查找和十大排序，而本篇将详细讲解其中的三大经典查找——跳跃查找、斐波那契查找、插值查找
    • 数据结构题库
      2023-06-19 17:32
      越来越不懂！的博客 【单选题】与数据元素本身的形式、内容、相对位置、个数无关的是数据的（ ）。 窗体顶端 A、逻辑结构 B、存储结构 C、逻辑实现 D、存储实现 窗体底端 正确答案： A :逻辑结构; 我的答案：A :逻辑结构; 得分： ...
    • 【考研408】算法与数据结构笔记
      2024-02-03 15:02
      newcih的博客 文章目录绪论数据结构的基本概念算法和算法评价线性表线性表的定义和基本操作线性表的顺序表示线性表的链式表示栈和队列栈基本操作栈的顺序存储结构栈的链式存储队列队列常见的基本操作队列的顺序存储结构队列的链式...
    • 『分块算法初步』
      2019-03-01 20:48
      weixin_33997389的博客 分块查找是折半查找和顺序查找的一种改进方法，分块查找由于只要求索引表是有序的，对块内节点没有排序要求，因此特别适合于节点动态变化的情况。 分块其实可以说是一种偏数据结构类的通用型算法吧，没有很艰深的...
    • 猹猹查叉叉『查找专题』
      2023-05-04 17:15
      @GSH1111的博客 查找表由同一类型的数据元素构成的集合查询元素是否在查找表中查找元素在查找表中的位置检索元素的各种属性插入一个元素删除一个元素根据记录的是键值或者记录是存储位置基于关键字比较的查找整型、浮点型、字符串的...
    • 大话数据结构 －－ 查找
      2018-09-06 21:24
      7Maggie_C的博客 查找，就是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）。 查找表（Search Table）是由同一类型的数据元素（或记录）组成的集合。 关键字（Key）是数据元素中某个数据项的值，又...
    • 数据结构答案
      2018-12-22 01:14
      xi邮lj的博客 第1章 绪论 一、基础知识题 ...【解答】数据是信息的载体，是描述客观事物的数、字符，以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。 数据元素是数据的基本单位。在不同...
    • 数据结构复习题
      2019-02-26 21:20
      沐游虞的博客 19.在数据结构中，与所有的计算机无关的是（ C ）  A．物理结构  B．存储结构  C．逻辑结构  D．逻辑和存储结构   20.下列四种基本逻辑机构中，数据元素之间关系最弱的是（A） A．集合 ...
    • 数据结构C语言版（答案）
      2012-09-15 22:27
      hrdzkj的博客 第1章 绪论 1.1 简述下列术语：数据，数据... 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。  数据对象是性质相同的数据元素的集合，是数据的一个子集。  数据结构是相互之间存在
    • 算法笔记day01
      2025-03-18 19:51
      梦想成为高手的菜鸟的博客 原始解法;循环遍历 2-这个数本身 (弊端:如果这个数很大,循环次数过多)优解:因为一个数的因子必定是两两相对应, ...输出结果:如果有重复元素涉及到多个数据,通常将这几个数据存储到数组或集合中,再返回前提:数据必须是有
    • 没有解决我的问题, 去提问

    问题事件

    • 系统已结题 5月7日
    • 创建了问题 4月29日