Comment prouver la notation Big Theta pour un programme?

Question

J'ai eu du mal à prouver une Big Theta Notation pour une fonction. Je peux comprendre comment on ferait pour prouver une Big Theta Notation quand un f (x) est explicitement mentionné, mais je ne sais pas comment vous feriez cela avec un programme.

Ci-dessous, j'ai écrit ce que je pensais être une définition courante de Big Theta Notation.

Dans le cas d'un programme, que serait f (x) et quel serait un bon moyen de prouver sa Big Theta Notation?

Par exemple, lorsque je regarde une boucle for imbriquée typique, j'imagine que sa grande notation thêta est Θ (n ² ), où n est le nombre d'itérations spécifié. Comment prouver cela en utilisant la définition Big Theta, en particulier lorsque je n'ai pas de f (x)?

Pour commencer, j'ai des devoirs où je dois prouver la Big Theta Notation d'un programme donné. Je veux juste des conseils généraux sur la façon dont je peux prouver la Big Theta Notation pour tout programme arbitraire.

Answer 1

Lors de l' étude de l'exécution d'un algorithme ou un programme, vous avez vraiment n'avez une$f(n)$ se cacher quelque part ($n$étant la taille de l'entrée). Le point de grand-$\Theta$ la notation consiste à oublier les termes constants ou insignifiants ennuyeux et à se concentrer sur le comportement asymptotique dominant (puisque les programmes sont souvent assez désordonnés).

Par exemple, supposons que nous voulions analyser le temps d'exécution d'un algorithme qui, étant donné une liste $A$ de $n$ éléments, compte le nombre de paires $(i,j)$ avec $i<j$ Pour qui $A[i]\neq A[j]$, puis renvoie ce nombre ainsi que le nombre maximum dans $A$. Une approche naïve serait:

• $c:=0$
• pour $j=0,\dots,n-1$
  • pour $i=0,\dots,j-1$
    • si $A[i]\neq A[j]$
      • $c \gets c+1$
• impression $c$

Si nous voulions analyser son exécution avec précision, nous aurions à tenir compte de nombreuses constantes de calcul ennuyeuses (comme le temps nécessaire pour modifier une variable, accéder à la mémoire, sauter entre les instructions). Depuis grand-$\Theta$est aveugle aux constantes, nous pouvons les ignorer. Ainsi, nous pouvons déterminer$f(n)$ être le nombre d'instructions de l'algorithme ci-dessus dans un monde idéalisé où toutes les instructions prennent le même temps.

Malheureusement, le nombre de calculs dépend également de $A$, sorte de. À savoir, à cause de la clause "if", nous exécutons uniquement le "$c\gets c+1$"instruction quand $A[i]\neq A[j]$. Cependant, grand-$\Theta$ nous sauve à nouveau ici: dans le meilleur des cas, nous n'exécuterons que l'instruction "if" dans chaque boucle (si $A$ est une liste de $n$copies de la même chose), et dans le pire des cas, nous exécuterons toujours l'instruction "if" et l' instruction "$c\gets c+1$"instruction (si $A$ est une liste de $n$éléments distincts). Nous sommes limités entre deux constantes, si grandes-$\Theta$nous permet de dire que cela n'a pas d'importance. Ainsi, nous pouvons simplifier$f(n)$ pour compter le contenu de cette boucle interne comme une seule instruction.

Retour aux instructions de comptage. Nous avons deux instructions qui prennent nos boucles en sandwich, puis la boucle interne se répète$j$ fois pour chacun $j$ allant de $0$ à $n-1$. Cela signifie que le nombre précis d'exécutions des doubles boucles est$\sum_{j=0}^{n-1}j = \frac{n(n-1)}2$.

Déjà, dans notre monde idéalisé ignorant les constantes de calcul et le branchement «si», nous obtenons $f(n) = \frac{n(n-1)}2+2$comme notre runtime. Dans la plupart des cas, cette quantité d'informations est trop d'informations, donc$\Theta$ revient pour nous simplifier la vie et nous permettre de conclure $f(n)\in\Theta(n^2)$, ce qui signifie que notre algorithme n'est qu'un algorithme de temps quadratique.

À la fin de la journée, grand-$\Theta$ (ou tout simplement grand-$O$en général) nous permet de simplifier nos analyses d'exécution en "comptant approximativement" le nombre d'itérations effectuées par nos boucles, et en les multipliant par un "approximatif" sur le temps qu'il faut aux instructions de la boucle pour s'exécuter. Bien sûr, vous devez être prudent lorsque vous faites des estimations "approximatives" (parfois, les boucles imbriquées ont la boucle interne se comportant de manière si sensible à la boucle externe que le temps d'exécution est bien meilleur que$\Theta(n^2)$comme le cas du tamis d'Eratosthène où son runtime est$O(n\log\log n)$), mais avec suffisamment de pratique, vous vous habituez à jouer au jeu et à reconnaître quand les boucles imbriquées sont $\Theta(n^2)$ ou soupçonner autrement.