El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència

HOME

Introducció

L'anàlisi de complexitat és una part fonamental de l'estudi dels algorismes. Ens permet entendre l'eficiència d'un algorisme en termes de temps i espai, i comparar diferents algorismes per determinar quin és més adequat per a un problema donat.

Objectius del Tema

Comprendre els conceptes bàsics de la complexitat temporal i espacial.
Aprendre a utilitzar la notació Big O, Big Ω i Big Θ.
Aplicar aquests conceptes per analitzar algorismes senzills.

Conceptes Bàsics

Complexitat Temporal

La complexitat temporal mesura el temps que un algorisme triga a executar-se en funció de la mida de l'entrada. Es representa comunament amb la notació Big O.

Complexitat Espacial

La complexitat espacial mesura la quantitat de memòria que un algorisme necessita durant la seva execució.

Notació Big O

La notació Big O descriu el pitjor cas de la complexitat temporal d'un algorisme. Ens diu com creix el temps d'execució a mesura que la mida de l'entrada augmenta.

Notació Big Ω

La notació Big Ω descriu el millor cas de la complexitat temporal d'un algorisme.

Notació Big Θ

La notació Big Θ proporciona una descripció ajustada de la complexitat temporal d'un algorisme, tant en el millor com en el pitjor cas.

Exemples de Complexitat

Exemple 1: Cerca Lineal

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

Complexitat Temporal: O(n)
Explicació: En el pitjor cas, hem de revisar tots els elements de l'array.

Exemple 2: Cerca Binària

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

Complexitat Temporal: O(log n)
Explicació: En cada iteració, l'algorisme redueix la mida de l'array a la meitat.

Exercicis Pràctics

Exercici 1: Anàlisi de Complexitat

Analitza la complexitat temporal dels següents algorismes:

Algorisme 1

def suma_elements(arr):
    suma = 0
    for i in arr:
        suma += i
    return suma

Complexitat Temporal: O(n)

Algorisme 2

def producte_elements(arr):
    producte = 1
    for i in arr:
        for j in arr:
            producte *= i * j
    return producte

Complexitat Temporal: O(n^2)

Exercici 2: Implementació i Anàlisi

Implementa un algorisme que trobi el màxim element en una matriu 2D i analitza la seva complexitat temporal.

def maxim_matriu(matriu):
    maxim = float('-inf')
    for fila in matriu:
        for element in fila:
            if element > maxim:
                maxim = element
    return maxim

Complexitat Temporal: O(n * m), on n és el nombre de files i m és el nombre de columnes.

Errors Comuns i Consells

Errors Comuns

No considerar el pitjor cas: És important analitzar l'algorisme en el seu pitjor cas per assegurar-se que és eficient en totes les situacions.
Confondre complexitat temporal i espacial: Assegura't de diferenciar clarament entre el temps d'execució i l'ús de memòria.

Consells

Practica amb diferents algorismes: La millor manera d'entendre la complexitat és analitzar molts algorismes diferents.
Utilitza eines de mesura: Hi ha eines que poden ajudar-te a mesurar el temps d'execució i l'ús de memòria dels teus algorismes.

Resum

En aquesta secció, hem après els conceptes bàsics de l'anàlisi de complexitat, incloent la notació Big O, Big Ω i Big Θ. Hem vist exemples pràctics i hem practicat l'anàlisi de complexitat amb exercicis. Aquestes habilitats són fonamentals per avaluar l'eficiència dels algorismes i seleccionar els més adequats per a cada problema.

En el següent tema, explorarem la recursió i la programació dinàmica, tècniques poderoses per dissenyar algorismes eficients.

Anàlisi de Complexitat