notation Big o pendant un certain temps en boucle qui utilisent le générateur aléatoire # comme conditions

Question

nous avons RNG qui génèrent n ° entre dans une boucle while [0.0,1000.0 [

nous comptons pour savoir combien de temps faut-il pour produire un n ° < 1,0.

code:

n =0 
while (RNG1000() >= 1.0){ 
n =+ 
} 

question: quel est le O

Answer 1

On dit qu'une fonction f de la variable n est grande-Oh d'une fonction g de la variable n - souvent notée f (n) = O (g (n)), ou f dans O (g) - s'il y a existe un n0 tel que pour tout n supérieur à n0, f (n) < = g (n). Supposons que le temps d'exécution de notre algorithme soit grand - Oh de certaines fonctions g de n. Alors il y a un n0 tel que pour n> n0, l'exécution de notre algorithme est inférieure ou égale à g (n). Choisissons un n '> n0 fixe et considérons ce que cela signifie: cela signifie que sur l'entrée n', notre algorithme est garanti pour se terminer dans les étapes g (n '). Nous devons avoir que g (n ') est un nombre; appelons ça t '. Donc, pour l'entrée n ', notre boucle ne peut pas prendre plus de t étapes. Mais ceci est manifestement faux, puisque - en supposant qu'une itération de boucle entière prenne une étape - la probabilité d'itération pour plus de t étapes est finie mais non nulle (en supposant que le RNG est un vrai RNG). C'est une contradiction, donc notre supposition que le temps d'exécution est grand - Oh de g était faux - c'est-à-dire qu'il n'y a pas de limite supérieure pour l'exécution.

Il est tentant de dire que c'est O (1) en termes de n, puisque la condition de la boucle ne dépend pas de n, mais cela est techniquement incorrect, compte tenu de l'analyse ci-dessus. Il n'y a vraiment pas de limite supérieure ici.

Answer 2

« notation Big O est une notation mathématique qui décrit le comportement limitant d'une fonction lorsque l'argument tend vers un particulier (?) valeur ou l'infini. "

La variable n dans votre cas ne contraint pas la limite supérieure d'une fonction. En fait, il n'y a pas de fonction dans ce cas (du moins pas de fonction qui renvoie des résultats reproductibles). Je suggérerais qu'il n'y a pas de notation Big O pour décrire cela et c'est undefined. Cependant, certains pourraient faire valoir que le pire des cas est simplement O (∞). Ce qui prête à confusion ici, c'est que vous n'utilisez pas réellement votre variable, n, pour contraindre votre comportement.