notation - nの観点からシータ表記を見つける

Question

x = x + 1以下のセグメントでステートメントが実行された回数について、nに関するΘ表記を見つけます。

i = 1
while (i < n^2)
    x = x + 1
    i = 3i

iの成長率はわかっていますが、の表記O(3^k)方法がわかりません。Θn

Answer 1

与えられた、前からn何回実行できるかを知る必要があります。あなたはすでにステップの後、あなたのタスクが解決していることを知っていますi = 3*ii = 1i >= n^2ki = 3^k

3^(k-1) < n^2 <= 3^k

、つまりk、の関数として書き込みnます。