0
FUNCTION SEEK(A,X)
1. FOUND = FALSE
2. K = 1
3. WHILE (NOT FOUND) AND (K < N)
   a.  IF (A[K] = X THEN
       1.  FOUND = TRUE
   b.  ELSE
       1.  K = K + 1
4. RETURN

分析这个算法(伪代码),我可以计算完成所需的步骤数,并用线性算法 Θ(n) 来分析它的效率。好的。

以下代码取决于循环内的内部公式才能完成:

1.  X = 1
2.  B = 1
3.  UNTIL (B > 100)
    a.  B = 2A - 2
    b.  A = A + 3

显然它不像第一个那么简单,我不能说循环重复 100 次,因为循环内 A 和 B 的增量不规则。我如何计算这个特定算法的步数以研究它的效率?

4

1 回答 1

2

B 取决于 A。A 单调递增。因此,循环根据 A 的初始值以线性时间运行。一些代数会告诉您 A 的什么值停止循环。

于 2012-10-04T02:30:33.013 回答