理纱默不作声地将电脑转向我们,屏幕上显示着如下所示的伪代码,每一行都标着用1或
表示的运行次数。
能找到
时顺序查找算法的运行次数
“
是什么?”泰朵拉问理纱。
“
的位置。”理纱简洁地回答。
“原来如此。”我看着整理好的算法说道,“原来是标注了从L1到L10每一行各自运行的次数啊……”
是啊!
在数学上经常应用这个方法啊。如果存在多种情况无法确定循环次数,用变量来表示就好了呀。导入变量
也就是
通过导入变量进行一般化。
“但是接下来该怎么做呢?”泰朵拉问。
“只要将各行的运行次数求和,不就可以求得整体的运行步数了嘛!”我说,“这个式子应该含有变量
。”
能找到
时顺序查找算法的运行步数
“也就是说,在能找到
的情况下,只要运行
步就可以得到输出!”泰朵拉说。
“没错。比如说,泰朵拉提到的测试用例要查找26,这时……”
“我来我来!我来算!”泰朵拉一下子提高了音量,“ 验算 ,对吧!”
“嗯,没错。”我和泰朵拉都清楚,推导出普遍公式后应该做的事情——用具体的例子验算。
“在刚才的测试用例
中,我们已经验证了能找到26这个数。26为数列中第4个数,所以
。”
“哦哦。”
“不出所料,结果为运行
步后流程结束吧。”
“嗯,这样就求出了:在能找到
的情况下流程的运行步数为
。那么下一个问题自然是,在数列中——”
“无法找到
的情况下,流程的运行步数是多少?”
泰朵拉接着我的话说道。
问题2-1(顺序查找算法的运行步数)
在数列
中无法找到
时,顺序查找算法的运行步数是多少呢?