En aquest tema, explorarem els diferents casos de complexitat que poden presentar els algorismes: el millor cas, el pitjor cas i el cas promig. Entendre aquests conceptes és fonamental per avaluar l'eficiència d'un algorisme en diferents situacions.
- Introducció als Casos de Complexitat
Quan analitzem la complexitat d'un algorisme, és important considerar com es comporta en diferents escenaris. Els tres casos principals són:
- Millor Cas: La situació en què l'algorisme té el rendiment més eficient possible.
- Pitjor Cas: La situació en què l'algorisme té el rendiment menys eficient possible.
- Cas Promig: Una situació intermèdia que representa el rendiment esperat de l'algorisme en la majoria dels casos.
- Millor Cas
El millor cas representa el temps mínim que un algorisme pot trigar en executar-se. Aquest cas és útil per entendre el rendiment òptim de l'algorisme, però no sempre és representatiu de la seva eficiència general.
Exemple: Cerca Lineal
En una cerca lineal, el millor cas es produeix quan l'element que busquem és el primer de la llista.
def cerca_lineal(arr, x):
for i in range(len(arr)):
if arr[i] == x:
return i
return -1
# Exemple d'ús
arr = [1, 2, 3, 4, 5]
x = 1
print(cerca_lineal(arr, x)) # Output: 0En aquest cas, la complexitat temporal és O(1) perquè només es fa una comparació.
- Pitjor Cas
El pitjor cas representa el temps màxim que un algorisme pot trigar en executar-se. Aquest cas és crucial per assegurar-nos que l'algorisme serà eficient fins i tot en les situacions més desfavorables.
Exemple: Cerca Lineal
En una cerca lineal, el pitjor cas es produeix quan l'element que busquem no es troba a la llista o és l'últim element.
def cerca_lineal(arr, x):
for i in range(len(arr)):
if arr[i] == x:
return i
return -1
# Exemple d'ús
arr = [1, 2, 3, 4, 5]
x = 6
print(cerca_lineal(arr, x)) # Output: -1En aquest cas, la complexitat temporal és O(n) perquè es recorren tots els elements de la llista.
- Cas Promig
El cas promig representa el temps esperat que un algorisme trigarà en executar-se en la majoria de les situacions. Aquest cas és sovint més representatiu del rendiment real de l'algorisme.
Exemple: Cerca Lineal
Per a la cerca lineal, el cas promig es pot calcular assumint que l'element que busquem es troba en una posició aleatòria de la llista.
def cerca_lineal(arr, x):
for i in range(len(arr)):
if arr[i] == x:
return i
return -1
# Exemple d'ús
arr = [1, 2, 3, 4, 5]
x = 3
print(cerca_lineal(arr, x)) # Output: 2En aquest cas, la complexitat temporal promig és O(n/2), que es simplifica a O(n).
- Comparació de Casos de Complexitat
La següent taula resumeix els diferents casos de complexitat per a la cerca lineal:
| Cas | Complexitat Temporal |
|---|---|
| Millor Cas | O(1) |
| Pitjor Cas | O(n) |
| Cas Promig | O(n) |
- Exercicis Pràctics
Exercici 1: Anàlisi de Complexitat de l'Ordenació per Inserció
Analitza els diferents casos de complexitat per a l'algorisme d'ordenació per inserció.
def ordenacio_per_insercio(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and key < arr[j]:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
# Exemple d'ús
arr = [5, 2, 9, 1, 5, 6]
ordenacio_per_insercio(arr)
print(arr) # Output: [1, 2, 5, 5, 6, 9]Solució:
- Millor Cas: La llista ja està ordenada. Complexitat: O(n).
- Pitjor Cas: La llista està ordenada en ordre invers. Complexitat: O(n^2).
- Cas Promig: La llista està en un ordre aleatori. Complexitat: O(n^2).
Exercici 2: Anàlisi de Complexitat de la Cerca Binària
Analitza els diferents casos de complexitat per a l'algorisme de 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
# Exemple d'ús
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
x = 4
print(cerca_binaria(arr, x)) # Output: 3Solució:
- Millor Cas: L'element es troba al mig de la llista. Complexitat: O(1).
- Pitjor Cas: L'element no es troba a la llista. Complexitat: O(log n).
- Cas Promig: L'element es troba en una posició aleatòria. Complexitat: O(log n).
- Conclusió
Entendre els diferents casos de complexitat és essencial per avaluar l'eficiència d'un algorisme en diverses situacions. El millor cas ens mostra el rendiment òptim, el pitjor cas ens assegura que l'algorisme serà eficient fins i tot en les pitjors situacions, i el cas promig ens dóna una idea del rendiment esperat en la majoria dels casos. Aquesta comprensió ens permet dissenyar i seleccionar algorismes més eficients per a les nostres necessitats.
En el següent mòdul, aprofundirem en les estratègies de disseny d'algorismes, començant amb la tècnica de "Divideix i Venceràs".
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