Introducció
L'anàlisi de la complexitat temporal és una part fonamental en l'estudi dels algorismes. Ens permet entendre com el temps d'execució d'un algorisme creix amb la mida de l'entrada. Això és crucial per avaluar l'eficiència i el rendiment dels algorismes, especialment quan es treballa amb grans volums de dades.
Conceptes Clau
- Complexitat Temporal
La complexitat temporal d'un algorisme mesura la quantitat de temps que necessita per completar-se en funció de la mida de l'entrada. Es representa comunament amb la notació Big-O.
- Notació Big-O
La notació Big-O descriu el comportament asimptòtic d'un algorisme, és a dir, com es comporta quan la mida de l'entrada tendeix a l'infinit. Alguns exemples comuns són:
- O(1): Temps constant
- O(log n): Temps logarítmic
- O(n): Temps lineal
- O(n log n): Temps quasi-lineal
- O(n^2): Temps quadràtic
- Anàlisi de Pitjor Cas, Millor Cas i Cas Promig
- Pitjor Cas (Worst-case): El temps màxim que pot trigar l'algorisme.
- Millor Cas (Best-case): El temps mínim que pot trigar l'algorisme.
- Cas Promig (Average-case): El temps esperat que trigarà l'algorisme en una entrada aleatòria.
Exemples Pràctics
Exemple 1: Cerca Lineal
La cerca lineal és un algorisme que busca un element en una llista recorrent-la des del principi fins al final.
def cerca_lineal(llista, element):
for i in range(len(llista)):
if llista[i] == element:
return i
return -1- Pitjor Cas: O(n) - L'element no està en la llista o és l'últim element.
- Millor Cas: O(1) - L'element és el primer de la llista.
- Cas Promig: O(n) - En una llista desordenada, es considera que l'element està en qualsevol posició amb igual probabilitat.
Exemple 2: Cerca Binària
La cerca binària és un algorisme eficient per trobar un element en una llista ordenada dividint repetidament la llista en dues meitats.
def cerca_binaria(llista, element):
esquerra, dreta = 0, len(llista) - 1
while esquerra <= dreta:
mig = (esquerra + dreta) // 2
if llista[mig] == element:
return mig
elif llista[mig] < element:
esquerra = mig + 1
else:
dreta = mig - 1
return -1- Pitjor Cas: O(log n) - L'element no està en la llista.
- Millor Cas: O(1) - L'element és al mig de la llista.
- Cas Promig: O(log n) - En una llista ordenada, es considera que l'element està en qualsevol posició amb igual probabilitat.
Exercicis Pràctics
Exercici 1: Anàlisi de Complexitat Temporal
Analitza la complexitat temporal dels següents algorismes i justifica la teva resposta.
Algorisme A
Algorisme B
Solucions
Algorisme A
- Pitjor Cas: O(n^2) - Hi ha dos bucles imbricats que recorren la llista n vegades cadascun.
Algorisme B
- Pitjor Cas: O(log n) - El valor de
ies duplica en cada iteració, per tant, el nombre d'iteracions és logarítmic en funció de n.
Resum
En aquesta secció, hem après sobre la importància de l'anàlisi de la complexitat temporal i com utilitzar la notació Big-O per descriure el rendiment dels algorismes. També hem vist exemples pràctics de cerca lineal i cerca binària, i hem practicat l'anàlisi de la complexitat temporal amb exercicis. Aquest coneixement és essencial per dissenyar algorismes eficients i optimitzar el rendiment del codi.
Curs d'Anàlisi i Disseny d'Algorismes
Mòdul 1: Introducció als Algorismes
Mòdul 2: Anàlisi d'Algorismes
- Anàlisi de Complexitat Temporal
- Anàlisi de Complexitat Espacial
- Cases de Complexitat: Millor, Pitjor i Promig
Mòdul 3: Estratègies de Disseny d'Algorismes
Mòdul 4: Algorismes Clàssics
- Cerca Binària
- Ordenació per Inserció
- Ordenació per Mescla (Merge Sort)
- Ordenació Ràpida (Quick Sort)
- Algorisme de Dijkstra
- Algorisme de Floyd-Warshall