Quelqu'un peut-il aider avec une grande notation O?

Question

void printScientificNotation(double value, int powerOfTen) 
{ 
if (value >= 1.0 && value < 10.0) 
{ 
    System.out.println(value + " x 10^" + powerOfTen); 
} 
else if (value < 1.0) 
{ 
    printScientificNotation(value * 10, powerOfTen - 1); 
} 
else  // value >= 10.0 
{ 
    printScientificNotation(value/10, powerOfTen + 1); 
} 

}

en supposant que imputs ne conduira pas à des boucles infinies

Je comprends comment la méthode va, mais je ne peux pas trouver un moyen de représenter la méthode. Par exemple, si la valeur était 0,00000009 ou 9e-8, la méthode appelle printScientificNotation (valeur * 10, powerOfTen-1); huit fois et System.out.println (valeur + "x 10 ^" + powerOfTen); une fois que.

Ainsi, il est appelé récursivement par l'exposant pour e. Mais comment est-ce que je représente cela par une grosse notation O?

Merci!

Answer 1

Est-ce une question piège? Ce code se répétera indéfiniment pour certaines de ses entrées (par exemple, value = -1.0, powerOfTen = 0), donc son exécution n'est pas O (f (n)) pour toute fonction finie f (n).

Modifier: En supposant value > 0.0 ...

Le temps d'exécution (ou la profondeur de récursivité, si vous préférez regarder cette façon) ne dépend pas de la valeur de powerOfTen, uniquement sur value. Pour une entrée initiale value dans la plage [1.0, 10.0), le temps d'exécution est constant, donc O (1), Pour value dans [10.0, + infini], vous divisez value par 10 pour chaque appel récursif jusqu'à value < 10.0, ainsi le l'exécution est O (log (value)). Un argument similaire peut être fait pour value dans l'intervalle (0,0,1.0), mais notez que le log value est négatif pour ce cas. Donc, votre réponse finale pourrait impliquer une opération de valeur absolue. Vous pouvez ensuite déterminer s'il est nécessaire de spécifier la base logarithmique dans le contexte d'une analyse de complexité asymptotique. J'espère que vous pouvez le prendre à partir de là!