특정 반복을 해결하는 알고리즘의 하한

Question

다음 재귀의 하한을 찾아야합니다.

$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)$ 달성 할 수 없거나 얻을 수 있습니까?

이런 것을 증명하기 위해 내가 아는 유일한 주된 방법은 적대적 주장이지만 몇 시간 동안 생각한 후에도 여전히 내가 원하는 것을 증명할 주장을 내놓을 수 없었습니다.

어떤 도움 / 팁 / 제안이라도 대단히 감사하겠습니다.

Answer 1

여기에 많은 혼란이 있습니다.

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$, 그러면 위의 두 인스턴스를 구분할 수 없으며 특히 그 중 적어도 하나에 대한 대답이 잘못됩니다.