performance - 如何分析这个算法的效率 Part 2

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

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

以下代码依赖于循环内部的内部公式才能完成，交易是代码中没有变量 N，因此该算法的效率将始终相同，因为我们将值 1 分配给A & B 变量：

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

现在我相信这个算法总是在恒定时间内执行。但是我如何使用代数来找出完成需要多少步骤？

Answer 1

是的，第二部分在 O(1) 时间内运行。您需要证明的唯一论点是每次它都会迭代一定次数。

代数上，A 每次增长 3，所以 B 每次增长 6。它将执行大约 100/6 次。