Vai al contenuto

Appunti del 10/05/2023⚓︎

Algoritmi di ricerca⚓︎

analizziamo due tipi, binaria e lineare o esaustiva.

lineare⚓︎

Text Only
1
2
3
4
5
6
7
8
9
trovato := 0
i := 0
ESEGUI
  SE (elemento in posizione i di a = x)
    ALLORA trovato := 1
  FINE
  i := i + 1
FINCHÉ (trovato = 0 AND i < n)
FINE

L'efficienza indica quanto l'algoritmo sia "buono" a cercare.

Indice iniziale Numero di confronti
0 1
1 2
2 3
... ...
n-1 n

con n numero di elementi dell'insieme.

binaria⚓︎

SOLO se l'insieme di partenza è ordinato.

confrontare valore x con elmeneto a[m] del vv a. se non sono uguali, ripetere con la parte di vettore a destra o sinistra dell'elemento centrale, in base al confronto.

Text Only
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
trovato := 0
inf, sup inizializzati
MENTRE (inf <= sup) AND (trovato = 0)
  m := parte_intera((inf + sup) / 2)
  SE (a > elemento in posizione m di a)
    ALLORA inf := m + 1
    ALTRIMENTI SE (x < elemento in posizione m di a)
      ALLORA trovato := 1
    FINE
  FINE
FINE
Passi Numero elementi
1 n = n/2^0
2 n/2 = n/2^1

la complessità è logaritmica è più bassa della lineare. n = 2^(k-1), k = log_2 n+1

Algoritmi di ordinamento⚓︎

prendere insieme di partenza ma restituirlo in ordine.

Selection sort⚓︎

a ogni passo k cerca la posizione del minimo e scambia il cal minimo con a[k].

se il vettore fosse già ordinato, avremmo comunque lo stesso numero di confronti. per ottenere complessità inferiori bisogna fare supposizioni sull'insieme di partenza.