Limite inférieure de l'algorithme résolvant certaines récidives

Question

Je dois trouver la borne inférieure de la récursivité suivante:

$A_1 = C_1 = p_1$, $B_1 = D_1 = 1-p_1$, $F_k = A_k + B_k$. Évaluer$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}

Dans ce cas, tous les numéros du formulaire $p_i$ reçoivent des entrées (il y a $n$ d'eux).

Je dois trouver la borne inférieure de cet algorithme.

Depuis son exécution est juste $O(n)$ (non?), je sais avec certitude que la valeur maximale possible de la borne inférieure est $\Omega(n)$. Comment pourrais-je prouver / réfuter cela$\Omega(n)$ est vraiment la limite minimale et que $\Omega(n-1)$ n'est pas / est réalisable?

La seule méthode principale que je connaisse pour prouver des choses comme celle-ci est un argument adverse, mais après quelques heures de réflexion, je n'ai toujours pas été en mesure de trouver un argument pour prouver ce que je veux.

Toute aide / astuce / suggestion serait grandement appréciée.

Answer 1

Il y a beaucoup de confusion ici:

1. $\Omega(n)$ et $\Omega(n-1)$ sont absolument les mêmes.
2. Vous n'avez pas d'argument adversaire pour montrer que cet algorithme fonctionne dans $\Theta(n)$. Il découle immédiatement de la description de l'argument.
3. Il existe une différence entre l'analyse du temps d'exécution d'un algorithme particulier et la démonstration que chaque algorithme qui résout correctement un problème doit s'exécuter en au moins autant d'étapes.

Afin de montrer que tout algorithme de calcul$F_n$ correctement doit fonctionner à temps $\Omega(n)$, nous montrerons qu'un tel algorithme doit lire toutes les entrées $p_1,\ldots,p_n$. Le point de départ est l'observation suivante:

La sortie correcte est différente pour les instances $p_1=\cdots=p_n=0$ et $p_1=\cdots=p_{i-1}=0,p_i=1,p_{i+1}=\cdots=p_n=0$.

Compte tenu de cela, nous pouvons utiliser un simple argument d'adversaire pour montrer que tout algorithme calculant correctement la fonction doit tout lire $p_j$. En effet, exécutez l'algorithme donné, en répondant$0$ chaque fois qu'il interroge la valeur de certains $p_j$. S'il annonce la réponse sans interroger, dites:$p_i$, alors il ne peut pas distinguer les deux instances ci-dessus, et en particulier, sa réponse sera erronée sur au moins l'une d'entre elles.