El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
HOME Els meus cursos Finalitzats
◄ Anterior
◄

Anàlisi de Complexitat Espacial

Següent ►
►

Introducció

L'anàlisi de la complexitat espacial és una part fonamental en el disseny i l'anàlisi d'algorismes. Mentre que la complexitat temporal es preocupa pel temps que un algorisme triga a executar-se, la complexitat espacial es preocupa per la quantitat de memòria que un algorisme necessita per executar-se. En aquest tema, explorarem els conceptes bàsics de la complexitat espacial, com calcular-la i com optimitzar l'ús de memòria en els nostres algorismes.

Conceptes Bàsics

Definició

La complexitat espacial d'un algorisme es refereix a la quantitat de memòria addicional que l'algorisme necessita a mesura que augmenta la mida de l'entrada. Aquesta memòria addicional inclou:

  • Memòria per a les variables locals: Memòria utilitzada per les variables dins de les funcions.
  • Memòria per a les estructures de dades: Memòria utilitzada per arrays, llistes, arbres, etc.
  • Memòria per a la pila de crides: Memòria utilitzada per mantenir el seguiment de les crides a funcions recursives.

Notació Asimptòtica

Igual que amb la complexitat temporal, utilitzem la notació asimptòtica per descriure la complexitat espacial. Les notacions més comunes són:

  • O(1): Memòria constant, independent de la mida de l'entrada.
  • O(n): Memòria lineal, proporcional a la mida de l'entrada.
  • O(n^2): Memòria quadràtica, proporcional al quadrat de la mida de l'entrada.

Exemples Pràctics

Exemple 1: Algorisme de Cerca Lineal

Considerem un algorisme de cerca lineal en un array:

def cerca_lineal(arr, x):
    for i in range(len(arr)):
        if arr[i] == x:
            return i
    return -1

Anàlisi de Complexitat Espacial:

  • Variables locals: i i x (O(1))
  • No hi ha estructures de dades addicionals.
  • No hi ha crides recursives.

Complexitat Espacial Total: O(1)

Exemple 2: Algorisme de Cerca Binària

Considerem un algorisme de cerca binària en un array ordenat:

def cerca_binaria(arr, x):
    esquerra, dreta = 0, len(arr) - 1
    while esquerra <= dreta:
        mig = (esquerra + dreta) // 2
        if arr[mig] == x:
            return mig
        elif arr[mig] < x:
            esquerra = mig + 1
        else:
            dreta = mig - 1
    return -1

Anàlisi de Complexitat Espacial:

  • Variables locals: esquerra, dreta, mig i x (O(1))
  • No hi ha estructures de dades addicionals.
  • No hi ha crides recursives.

Complexitat Espacial Total: O(1)

Exemple 3: Algorisme de Fibonacci Recursiu

Considerem un algorisme recursiu per calcular el n-èssim número de Fibonacci:

def fibonacci(n):
    if n <= 1:
        return n
    else:
        return fibonacci(n-1) + fibonacci(n-2)

Anàlisi de Complexitat Espacial:

  • Variables locals: n (O(1))
  • No hi ha estructures de dades addicionals.
  • Crides recursives: Cada crida recursiva ocupa espai a la pila de crides.

Complexitat Espacial Total: O(n) (degut a la profunditat de la recursió)

Exercicis Pràctics

Exercici 1: Anàlisi de Complexitat Espacial d'un Algorisme de Ordenació per Selecció

Analitza la complexitat espacial del següent algorisme d'ordenació per selecció:

def ordenacio_per_seleccio(arr):
    n = len(arr)
    for i in range(n):
        min_index = i
        for j in range(i+1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        arr[i], arr[min_index] = arr[min_index], arr[i]
    return arr

Solució:

  • Variables locals: n, i, min_index, j (O(1))
  • No hi ha estructures de dades addicionals.
  • No hi ha crides recursives.

Complexitat Espacial Total: O(1)

Exercici 2: Anàlisi de Complexitat Espacial d'un Algorisme de Ordenació per Fusió (Merge Sort)

Analitza la complexitat espacial del següent algorisme d'ordenació per fusió:

def merge_sort(arr):
    if len(arr) > 1:
        mig = len(arr) // 2
        esquerra = arr[:mig]
        dreta = arr[mig:]

        merge_sort(esquerra)
        merge_sort(dreta)

        i = j = k = 0

        while i < len(esquerra) and j < len(dreta):
            if esquerra[i] < dreta[j]:
                arr[k] = esquerra[i]
                i += 1
            else:
                arr[k] = dreta[j]
                j += 1
            k += 1

        while i < len(esquerra):
            arr[k] = esquerra[i]
            i += 1
            k += 1

        while j < len(dreta):
            arr[k] = dreta[j]
            j += 1
            k += 1

    return arr

Solució:

  • Variables locals: mig, esquerra, dreta, i, j, k (O(1))
  • Estructures de dades addicionals: esquerra i dreta (O(n) per cada nivell de recursió)
  • Crides recursives: Cada crida recursiva ocupa espai a la pila de crides.

Complexitat Espacial Total: O(n) (degut a les còpies temporals esquerra i dreta)

Resum

En aquesta secció, hem après què és la complexitat espacial i com analitzar-la. Hem vist exemples pràctics d'algorismes amb diferents complexitats espacials i hem practicat l'anàlisi de la complexitat espacial amb exercicis. La comprensió de la complexitat espacial és crucial per dissenyar algorismes eficients que no només siguin ràpids, sinó que també utilitzin la memòria de manera eficient.

◄ Anterior
◄
Següent ►
►
El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
© Copyright 2024. Tots els drets reservats