Arborescence récursive/complexité temporelle Affectation de schéma

Question

Si vous pouviez m'aider avec TOUTE partie de cette question, je l'apprécierais. Merci.

2^0 = 1 
2^N = 2^(N-1) + 2^(N-1) 

1. Convertir cette définition en une fonction récursive arbre exactement équivalent appelé deux à la puissance de. Décrivez sa complexité temporelle asymptotique et expliquez pourquoi elle a cette complexité de temps.

2. Maintenant, écrivez une fonction appelée tttpo_rec qui calcule exactement la même chose, mais qui utilise un processus récursif linéaire qui a une complexité de temps O (n) et utilise également l'espace O (n) pour ses opérations en attente.

3. Maintenant, écrivez une fonction appelée tttpo_iter qui calcule exactement la même chose, mais qui utilise un processus itératif linéaire qui a une complexité de temps O (n) et utilise également un espace constant. Supposons maintenant que vous vouliez généraliser l'une des définitions précédentes afin qu'elle gère des pouvoirs entiers arbitraires, de sorte que vous puissiez calculer 2^N, 3^N, etc. Écrivez une fonction appelée to-the-power- de cela prend deux arguments et élève l'un au pouvoir de l'autre.

Voici le modèle:

;; to-the-power-of: integer integer -> integer 
;; This function raises m to the power of n, returning the result. 
;; m must be > 0 and n >= 0. 
(define (to-the-power-of m n) 
    ...) 

(check-expect (to-the-power-of 1 0) 1) ; base case 
(check-expect (to-the-power-of 2 3) 8) ; recursive case 
(check-expect (to-the-power-of 3 2) 9) ; recursive case 

Nous allons ajouter une restriction: vous ne pouvez pas utiliser l'opérateur *; vous ne pouvez utiliser la fonction récursive suivante pour faire multiplications:

;;; multiply: integer integer -> integer 
;; This function multiplies two non-negative integers, returning the result. 
;; Its time complexity is O(a). 
(define (multiply a b) 
    ...) 

Exprimer la fonction et à décrire la complexité de temps et pourquoi.

Answer 1

Hahahaha. Je ne devrais pas faire de devoirs pour les gens, mais c'est trop amusant. :-P

1. Ceci est juste l'implémentation naïve. Je peux répondre à cette question sans donner le reste des questions. De toute évidence, il s'agit d'une implémentation vraiment stupide, mais vous êtes invité à donner sa complexité asymptotique. Pensez à éviter d'appeler tttpo deux fois par itération. Comme il vous est demandé d'éviter d'utiliser *, vous devrez peut-être stocker le résultat de tttpo.

2. Lire sur la récurrence de la queue. Pour être précis, vous devez savoir comment convertir un algorithme récursif général en sa version équivalente itérative (ou récursive en queue, puisqu'il s'agit d'un schéma).

3. Obvious une fois que vous avez écrit le code 3. (Ou bien, montrez-moi votre réponse à 3 et je vais vous aider.)

Bonne chance!

Answer 2

Le premier algorithme est O (2^n), et peut être écrit comme suit:

(define (2pow x) 
    (if (= x 0) 1 
     (+ (2pow (- x 1)) 
     (2pow (- x 1))))) 

Cela peut être réécrite en O (n) comme suit:

(define (2pow x) 
    (if (= x 0) 1 
    (* 2 (2pow (- x 1))))) 

Depuis Scheme utilise l'optimisation des appels de queue, on peut écrire cela comme une fonction récursive qui prend pile constante:

(define (2pow x) 
    (define (internal x accum) 
    (if (= x 0) accum 
     (internal (- x 1) (* accum 2)))) 
    (internal x 1)) 

Generaliz ed:

(define (to-the-power-of a b) 
    (define (internal x accum) 
    (if (= x 0) accum 
     (internal (- x 1) (* accum a)))) 
    (internal b 1)) 

modifier: depuis que je vois que vous ne pouvez pas utiliser *, vous pouvez simplement écrire votre propre multiplication entier:

(define (mult a b) 
    (define (internal a accum) 
    (if (= a 1) accum 
     (internal (- a 1) (+ accum b)))) 
    (internal a b)) 

C'est récursive, de sorte qu'il fonctionne en constante empiler l'espace. Remplacez simplement * par mult dans l'un des algorithmes ci-dessus.

Je devrais également noter que toutes ces fonctions ont été écrites directement ici dans l'éditeur sans être testées. utiliser à vos risques et périls