La notació asimptòtica és una eina fonamental en l'anàlisi d'algorismes, ja que permet descriure el comportament de la complexitat temporal i espacial dels algorismes de manera abstracta i independent del maquinari o la implementació específica. En aquesta secció, explorarem els conceptes bàsics de la notació asimptòtica, incloent-hi les notacions més comunes: O gran, Ω gran i Θ gran.

La notació asimptòtica s'utilitza per descriure el creixement de la complexitat d'un algorisme en funció de la mida de l'entrada. Ens permet comparar l'eficiència d'algorismes de manera teòrica.

• Comparació d'algorismes: Permet comparar diferents algorismes per a la mateixa tasca.
• Escalabilitat: Ajuda a entendre com es comportarà un algorisme a mesura que la mida de l'entrada creix.
• Optimització: Facilita la identificació de colls d'ampolla en el rendiment.

La notació O gran descriu un límit superior del temps d'execució d'un algorisme. És a dir, proporciona una cota superior del creixement de la funció de complexitat.

Definició Formal: \[ f(n) = O(g(n)) \] si existeixen constants positives \( c \) i \( n_0 \) tals que: \[ 0 \leq f(n) \leq c \cdot g(n) \quad \text{per a tot} \ n \geq n_0 \]

Exemple: Si tenim una funció \( f(n) = 3n^2 + 2n + 1 \), podem dir que \( f(n) = O(n^2) \) perquè, per a \( n \) suficientment gran, \( 3n^2 \) domina els altres termes.

La notació Ω gran descriu un límit inferior del temps d'execució d'un algorisme. Proporciona una cota inferior del creixement de la funció de complexitat.

Definició Formal: \[ f(n) = \Omega(g(n)) \] si existeixen constants positives \( c \) i \( n_0 \) tals que: \[ 0 \leq c \cdot g(n) \leq f(n) \quad \text{per a tot} \ n \geq n_0 \]

Exemple: Si tenim una funció \( f(n) = 3n^2 + 2n + 1 \), podem dir que \( f(n) = \Omega(n^2) \) perquè, per a \( n \) suficientment gran, \( 3n^2 \) és el terme dominant.

La notació Θ gran descriu una cota ajustada del temps d'execució d'un algorisme. Indica que una funció creix exactament al mateix ritme que una altra funció.

Definició Formal: \[ f(n) = \Theta(g(n)) \] si existeixen constants positives \( c_1, c_2 \) i \( n_0 \) tals que: \[ 0 \leq c_1 \cdot g(n) \leq f(n) \leq c_2 \cdot g(n) \quad \text{per a tot} \ n \geq n_0 \]

Exemple: Si tenim una funció \( f(n) = 3n^2 + 2n + 1 \), podem dir que \( f(n) = \Theta(n^2) \) perquè \( 3n^2 \) és el terme dominant i els altres termes són insignificants per a \( n \) gran.

Determina la notació asimptòtica per a les següents funcions:

1. \( f(n) = 5n^3 + 2n^2 + n \)
2. \( g(n) = 4n \log n + 20 \)
3. \( h(n) = 2^n + n^2 \)

Solucions:

1. \( f(n) = O(n^3) \), \( f(n) = \Omega(n^3) \), \( f(n) = \Theta(n^3) \)
2. \( g(n) = O(n \log n) \), \( g(n) = \Omega(n \log n) \), \( g(n) = \Theta(n \log n) \)
3. \( h(n) = O(2^n) \), \( h(n) = \Omega(2^n) \), \( h(n) = \Theta(2^n) \)

Classifica les següents funcions en ordre creixent de complexitat:

1. \( n \log n \)
2. \( n^2 \)
3. \( 2^n \)
4. \( n! \)
5. \( \log n \)

Solució: \[ \log n < n \log n < n^2 < 2^n < n! \]

En aquesta secció, hem après sobre la notació asimptòtica i les seves tres formes principals: O gran, Ω gran i Θ gran. Hem vist com aquestes notacions ens ajuden a descriure el comportament de la complexitat dels algorismes de manera abstracta i independent de la implementació específica. També hem practicat amb alguns exercicis per reforçar els conceptes apresos. En el següent mòdul, aprofundirem en l'anàlisi de la complexitat temporal dels algorismes.