En aquesta secció, treballarem amb exercicis pràctics per reforçar els conceptes d'anàlisi de complexitat temporal i espacial. Aquests exercicis estan dissenyats per ajudar-te a comprendre com avaluar l'eficiència dels algorismes i identificar les seves limitacions.

Considera el següent algorisme que calcula la suma de tots els elements d'una matriu bidimensional:

1. Quin és el temps d'execució d'aquest algorisme en termes de la notació Big-O?
2. Com canviaria la complexitat temporal si la matriu fos tridimensional?

1. Anàlisi de Complexitat Temporal:

   • L'algorisme té dos bucles for imbricats. Si n és el nombre de files i m és el nombre de columnes, el temps d'execució és proporcional al producte n * m.
   • Per tant, la complexitat temporal és O(n * m).

2. Matriu Tridimensional:

   • Si la matriu fos tridimensional, tindríem un altre bucle for imbricat.
   • Suposem que la matriu té dimensions n x m x p. L'algorisme seria:

   def suma_matriz_tridimensional(matriz):
       suma = 0
       for capa in matriz:
           for fila in capa:
               for elemento in fila:
                   suma += elemento
       return suma
   

   • En aquest cas, la complexitat temporal seria O(n * m * p).

Considera el següent algorisme que crea una llista amb els quadrats dels primers n nombres enters:

1. Quin és l'espai addicional utilitzat per aquest algorisme en termes de la notació Big-O?
2. Com canviaria la complexitat espacial si, en lloc de guardar els quadrats en una llista, només imprimíssim els quadrats?

1. Anàlisi de Complexitat Espacial:

   • L'algorisme crea una llista de longitud n per emmagatzemar els quadrats dels nombres.
   • Per tant, l'espai addicional utilitzat és O(n).

2. Imprimir en lloc de guardar:

   • Si només imprimíssim els quadrats i no els guardéssim en una llista, l'espai addicional utilitzat seria constant, ja que no necessitem emmagatzemar els resultats.
   • La complexitat espacial seria O(1).

   def imprimir_quadrats(n):
       for i in range(n):
           print(i * i)
   

Considera el següent algorisme que troba el màxim element en una llista i després crea una nova llista amb els elements que són menors que aquest màxim:

1. Quin és el temps d'execució d'aquest algorisme en termes de la notació Big-O?
2. Quin és l'espai addicional utilitzat per aquest algorisme en termes de la notació Big-O?

1. Anàlisi de Complexitat Temporal:

   • La funció max(llista) té una complexitat temporal de O(n), on n és la longitud de la llista.
   • El bucle for també té una complexitat temporal de O(n), ja que recorre tots els elements de la llista.
   • Per tant, la complexitat temporal total de l'algorisme és O(n) + O(n) = O(n).

2. Anàlisi de Complexitat Espacial:

   • La nova llista nova_llista pot contenir fins a n-1 elements en el pitjor dels casos (quan tots els elements són diferents i només un és el màxim).
   • Per tant, l'espai addicional utilitzat és O(n).

Considera el següent algorisme recursiu que calcula el n-è nombre de la sèrie de Fibonacci:

1. Quin és el temps d'execució d'aquest algorisme en termes de la notació Big-O?
2. Com canviaria la complexitat temporal si utilitzéssim memòria intermèdia (memoization)?

1. Anàlisi de Complexitat Temporal:

   • L'algorisme recursiu de Fibonacci fa dues crides recursives per cada valor de n, excepte per als casos base.
   • Això crea un arbre de recursió exponencial, amb una complexitat temporal de O(2^n).

2. Memoization:

   • Si utilitzem memòria intermèdia per emmagatzemar els resultats de les crides recursives ja calculades, podem reduir la complexitat temporal a O(n).
   • Exemple amb memoization:

   def fibonacci_memo(n, memo={}):
       if n in memo:
           return memo[n]
       if n <= 1:
           return n
       memo[n] = fibonacci_memo(n-1, memo) + fibonacci_memo(n-2, memo)
       return memo[n]
   

En aquesta secció, hem treballat amb diversos exercicis per analitzar la complexitat temporal i espacial d'algorismes. Hem vist com identificar la complexitat en algorismes iteratius i recursius, així com l'impacte de l'ús de memòria intermèdia en la millora de l'eficiència. Aquests conceptes són fonamentals per dissenyar algorismes eficients i optimitzar el rendiment del codi.