algorithm - 如何分析这个算法的效率

Question

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

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

以下代码依赖于循环内的内部公式来完成:

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

显然不像第一个那么简单，而且我不能说循环重复100次，因为循环内部A和B的不规则递增。如何计算此特定算法的步骤数以研究其效率？

Answer 1

B 依赖于 A。 A 单调递增。 因此，循环以线性时间运行，具体取决于 A 的初始值。 一点点代数就会告诉你什么 A 值停止循环。