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

このアルゴリズム (疑似コード) を分析すると、完了するまでに必要なステップ数を数えることができ、線形アルゴリズムであるシータ表記 Θ(n) でその効率を分析できます。わかった。

次のコードは、終了するためにループ内の内部式に依存しています。

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

明らかに最初のものほど単純ではなく、ループ内の A と B のインクリメントが不規則であるため、ループが 100 回繰り返されるとは言えません。効率を調べるために、この特定のアルゴリズムのステップ数をカウントするにはどうすればよいですか?

Answer 1

B は A に依存します。A は単調増加します。したがって、ループは A の初期値に応じて線形時間で実行されます。少し代数を使用すると、A のどの値がループを停止するかがわかります。