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

はい、この 2 番目の部分は O(1) 時間で実行されます。それを証明する必要がある唯一の議論は、毎回設定された回数反復するということです。

代数的に、A は毎回 3 ずつ増加するので、B は毎回 6 ずつ増加します。およそ 100/6 回実行されます。