购买
下载掌阅APP,畅读海量书库
立即打开
畅读海量书库
扫码下载掌阅APP

2.1.6 顺序查找算法分析(能找到 \boldsymbol{v} 的情况)

理纱默不作声地将电脑转向我们,屏幕上显示着如下所示的伪代码,每一行都标着用1或 M 表示的运行次数。

能找到 \boldsymbol{v} 时顺序查找算法的运行次数

M 是什么?”泰朵拉问理纱。

v 的位置。”理纱简洁地回答。

“原来如此。”我看着整理好的算法说道,“原来是标注了从L1到L10每一行各自运行的次数啊……”

是啊!

在数学上经常应用这个方法啊。如果存在多种情况无法确定循环次数,用变量来表示就好了呀。导入变量 M 也就是

通过导入变量进行一般化。

“但是接下来该怎么做呢?”泰朵拉问。

“只要将各行的运行次数求和,不就可以求得整体的运行步数了嘛!”我说,“这个式子应该含有变量 M 。”

能找到 v 时顺序查找算法的运行步数

\begin{aligned}&={\rm L1+L2+L3+L4+L5+L6+L7+L8+L9+L10}\\&=1+1+M+M+1+0+(M-1)+(M-1)+0+1\\&=M+M+M+M+1+1+1+1-1-1\\&=4M+2\end{aligned}

“也就是说,在能找到 v 的情况下,只要运行 4M+2 步就可以得到输出!”泰朵拉说。

“没错。比如说,泰朵拉提到的测试用例要查找26,这时……”

“我来我来!我来算!”泰朵拉一下子提高了音量,“ 验算 ,对吧!”

“嗯,没错。”我和泰朵拉都清楚,推导出普遍公式后应该做的事情——用具体的例子验算。

“在刚才的测试用例 {31,~41,~59,~26,~53\} 中,我们已经验证了能找到26这个数。26为数列中第4个数,所以 M=4 。”

“哦哦。”

“不出所料,结果为运行 4M+2=18 步后流程结束吧。”

“嗯,这样就求出了:在能找到 v 的情况下流程的运行步数为 4M+2 。那么下一个问题自然是,在数列中——”

“无法找到 v 的情况下,流程的运行步数是多少?”

泰朵拉接着我的话说道。

问题2-1(顺序查找算法的运行步数)

在数列 A={A[1],A[2],A[3],\cdots,A[n]\} 中无法找到 v 时,顺序查找算法的运行步数是多少呢? l6LV/1ZHSMTJ1fg3M/wURKyRO2P+MaU9p70Mf1z3IjVsrdUDkBwMuBh43oRonhoE

点击中间区域
呼出菜单
上一章
目录
下一章
×