J'ai écrit la solution suivante pour un défi mais je ne suis pas sûr de sa complexité temporelle:
def ASCIIConversion(string):
newStr = ''
for chr in string:
if chr.isspace():
newStr = newStr + ' '
else:
newStr += str(ord(chr))
return newStr
Est-ce la complexité du programme, O (logn), à cause de l'instruction else ?
3 Réponses :
Cette solution est toujours O (n). Je ne suis pas tout à fait sûr de savoir pourquoi la déclaration else affecterait cela, en fait. Vous effectuez une opération sur chaque caractère de la chaîne.
Même si pour chaque personnage, vous exécutez plusieurs instructions (comparaisons, etc.), vous pouvez penser que la complexité est quelque chose comme O (3n), mais bien sûr vous ne tenez pas compte du coefficient. Je suis sûr que vous le savez, mais pour les personnes qui verront cette question à l'avenir, qui ne comprendront pas la déclaration else, cela pourrait aider.
J'apprends en fait la notation Big O en ce moment, et il semble que j'ai des idées fausses. Merci pour la réponse approfondie!
@cpit pas de problème! En règle générale, vous pouvez simplement compter le nombre de boucles for et while et le calculer à partir de là.
Indépendamment de la condition if-else, parcourez en boucle chaque caractère de la chaîne de sorte que la complexité en temps soit O (n).
La complexité temporelle dans le pire des cas est calculée comme ci-dessous (supposons que la longueur maximale de la chaîne soit n):
newStr = '' # will be done once so 1 time.
for chr in string: # is iterating on the input with max length of n so n times.
if chr.isspace(): # will be checked once it is in the loop so 1 time per each iteration.
newStr = newStr + ' ' # also once per iteration if the if condition is satisfied
else: # will be chehcked once per iteration
newStr += str(ord(chr)) # if else is satisfied
return newStr # will be done 1 time.
nous supposerons que les temps constants sont c donc:
Complexité temporelle = 1 + n (c * c + c * c) + 1 = 2 + Cn => O (n)
@TrebuchetMS Merci. Terminé :)
vous parcourez le tableau de chaînes, qui devrait être
O (n). toutes les instructions à l'intérieur de la boucle sont en temps constant, y compris if et else.J'apprends en fait la notation Big O en ce moment, et il semble que j'ai des idées fausses. Merci!