青岛网站建设公司怎么选,购买域名和服务器,网站开发培训太原,自应式网站【问题描述】 邓俊辉的《数据结构#xff08;C语言版#xff09;#xff08;第3版#xff09;》#xff08;ISBN#xff1a;9787302330646#xff09;中#xff0c;开始于第48页的“2.6.5 二分查找#xff08;版本A#xff09;”内容在第50页详述了“成功查找长度”的…【问题描述】 邓俊辉的《数据结构C语言版第3版》ISBN9787302330646中开始于第48页的“2.6.5 二分查找版本A”内容在第50页详述了“成功查找长度”的递推式但此递推式乍一看令人费解。故为了说明问题进行一些约定并详述如下 ● 既然是二分查找所以给定的序列必定是有序的。 ● 不失一般性约定有序序列的长度 这样便可构建一个高度为 k 的满的二分查找树。 ● 设 C(k) 表示高度为 k 的满的二分查找树中所有元素的查找长度总和。此时问题就可以用递归方法求解。即 k 层的满二叉树可以转化为左右两个 k-1 层的满二叉树。 依据邓俊辉《数据结构C语言版第3版》ISBN9787302330646中“2.6.5 二分查找版本A”的算法陈述可知 1第 k 层的查找长度为2也即 2且稍加观察会发现左面的 k-1 层的子树所有元素的查找长度都会相对于以第 k-1 层为顶层时的查找长度多1左子树共多 。 3同样右面的 k-1 层的子树所有元素的查找长度都会相对于以第 k-1 层为顶层时的查找长度多2右子树共多 。 所以根据递归算法的设计思想需要把这些长度补上共同构成 C(k)。 综上可得 C(k) 的递推公式如下 化简得 若令 则有 故利用上文得出的 可进一步得出 于是将 代入 可得 从而可得平均查找长度为 忽略掉低阶项、常数项、系数项可得本版本的二分查找的平均查找长度的时间复杂度为
【参考文献】https://ask.csdn.net/questions/699067https://www.bilibili.com/video/BV1C54y1L7JM/https://www.bilibili.com/video/BV1C54y1L7JM/?p76vd_sourcefea4f130ba05b1c873be1db0c639fc56https://blog.csdn.net/hnjzsyjyj/article/details/133100051https://blog.csdn.net/qq_33499861/article/details/105103708
