特定の再発を解決するアルゴリズムの下限

Nov 20 2020

次の再帰の下限を見つける必要があります。

$A_1 = C_1 = p_1$$B_1 = D_1 = 1-p_1$$F_k = A_k + B_k$。評価する$F_n$\begin{align} A_{k+1} &= (A_k + 2C_k) p_{k+1} + (1-p_k) p_{k+1}, \\ B_{k+1} &= (B_k + 2D_k) (1-p_{k+1}) + p_k (1-p_{k+1}), \\ C_{k+1} &= C_k p_{k+1} + (1-p_k) p_{k+1}, \\ D_{k+1} &= D_k (1-p_{k+1}) + p_k (1-p_{k+1}). \end{align}

この場合、フォームのすべての番号 $p_i$ 入力が与えられます( $n$ そのうちの)。

このアルゴリズムの下限を見つける必要があります。

ランタイムなので $O(n)$ (右?)、私は確かに下限の可能な最大値が $\Omega(n)$。それを証明/反証するにはどうすればよいですか$\Omega(n)$ 本当に最小の限界であり、それは $\Omega(n-1)$ 達成できない/達成できない?

このようなことを証明するために私が知っている唯一の主な方法は敵対者の議論ですが、数時間考えた後、私はまだ私が欲しいものを証明するための議論を思い付くことができませんでした。

任意のヘルプ/ヒント/提案をいただければ幸いです。

回答

YuvalFilmus Nov 20 2020 at 14:49

ここにはかなり多くの混乱があります:

  1. $\Omega(n)$ そして $\Omega(n-1)$ まったく同じです。
  2. このアルゴリズムがで実行されることを示すための敵対的な議論はありません $\Theta(n)$。引数の説明の直後に続きます。
  3. 特定のアルゴリズムの実行時間を分析することと、問題を正しく解決するすべてのアルゴリズムを少なくとも非常に多くのステップで実行する必要があることを示すことには違いがあります。

ことを示すために任意のアルゴリズムは、コンピューティング$F_n$ 正しく実行する必要があります $\Omega(n)$、そのようなアルゴリズムはすべての入力を読み取る必要があることを示します $p_1,\ldots,p_n$。出発点は次の観察です:

正しい出力はインスタンスによって異なります $p_1=\cdots=p_n=0$ そして $p_1=\cdots=p_{i-1}=0,p_i=1,p_{i+1}=\cdots=p_n=0$

それを考えると、単純な敵対者の引数を使用して、関数を正しく計算するアルゴリズムはすべてを読み取る必要があることを示すことができます $p_j$。確かに、与えられたアルゴリズムを実行し、答えます$0$ いくつかの値を照会するときはいつでも $p_j$。クエリせずに回答をアナウンスする場合は、たとえば、$p_i$の場合、上記の2つのインスタンスを区別することはできません。特に、少なくとも1つのインスタンスでその答えが間違っています。