complexité temporelle de la fonction composite en termes de n

Question

En supposant n est un entier positif, la fonction composite fonctionne comme suit:

(define (composite? n) 
    (define (iter i) 
    (cond ((= i n) #f) 
      ((= (remainder n i) 0) #t) 
      (else (iter (+ i 1))))) 
    (iter 2)) 

Il me semble que la complexité du temps (avec une limite étanche) est ici O (n) ou plutôt gros thêta (n). Je suis juste en train de le regarder en ce moment. Puisque nous ajoutons 1 à l'argument de iter à chaque fois que nous passons en boucle, il semble que ce soit O (n). Y a-t-il une meilleure explication?

Answer 1

La fonction telle qu'écrite est O (n). Mais si vous changez le test (= i n) en (< n (* i i)) la complexité temporelle tombe à O (sqrt (n)), ce qui est une amélioration considérable; si n est un million, la complexité temporelle passe d'un million à un millier. Ce test fonctionne parce que si n = pq, l'un de p et q doit être inférieur à la racine carrée de n tandis que l'autre est supérieur à la racine carrée de n; ainsi, si aucun facteur n'est trouvé inférieur à la racine carrée de n, n ne peut pas être composite. La réponse de Newacct suggère correctement que le coût de l'arithmétique importe si n est grand, mais le coût de l'arithmétique est log log n, pas log n comme le suggère newacct.

Answer 2

Différentes personnes vous donneront des réponses différentes en fonction de ce qu'elles supposent et de ce qu'elles prennent en compte dans le problème.

O (n) suppose que les opérations d'égalité et de reste que vous faites dans chaque boucle sont O (1). Il est vrai que le processeur les fait dans O (1), mais cela ne fonctionne que pour les nombres à précision fixe. Puisque nous parlons de complexité asymptotique, et puisque «asymptotique», par définition, traite de ce qui se passe quand les choses se développent sans limite, nous devons considérer les nombres qui sont arbitrairement grands. (Si les nombres dans votre problème étaient bornés, alors le temps de fonctionnement de l'algorithme serait également borné, et donc l'algorithme entier serait techniquement O (1), évidemment pas ce que vous voulez.)

Pour une précision arbitraire nombres, je dirais que l'égalité et le reste en général prennent du temps proportionnel à la taille du nombre, qui est log n. (À moins que vous ne puissiez l'optimiser dans une analyse amortie d'une manière ou d'une autre) Donc, si nous considérons cela, l'algorithme serait O (n log n). Certains pourraient considérer que cela est nitpicky