算法中的步数法

步数法是分析算法的一种方法。在这种方法中，我们计算一条指令执行的次数。由此，我们将尝试找到算法的复杂度。

假设我们有一个算法来执行顺序搜索。假设每条指令执行需要 c1、c2、…… 的时间，那么我们将尝试找出该算法的时间复杂度。

现在，如果我们通过将执行次数乘以代价来累加代价（考虑最坏情况），我们将得到

                  代价=c1+(n+1)c 2+nc3+c 4+c 5

                  代价=c1+nc 2+c2+nc 3+c 4+c5

                  代价=n(c 2+c3)+c 1+c 4+c5

                  代价=n(c 2+c3)+C

考虑到 c1 + c4 + c5 为 C，因此最终方程类似于直线 y = mx + b。因此，我们可以说该函数是线性的。复杂度将为 O(n)。

Arnab Chakraborty

更新于： 2019年8月27日

9K+ 浏览量

启动您的 职业生涯

通过完成课程获得认证

开始