Intro alla complessità e algoritmi di ricerca Flashcards
(7 cards)
Ricerca sequenziale come funziona l’algoritmo?
Che complessità ha l’algoritmo?
L’algoritmo analizza tutti gli elementi della lista finché non trova l’elemento k. Se lo trova si interrompe, altrimenti scorre tutta la lista e poi si ferma.
Complessità O(n)
Ricerca sequenziale sapendo che la lista è ordinata.
Che complessità ha? Come differisce da quello precedente?
Uguale a ricerca sequenziale sono che se troviamo un numero maggiore di k allora l’algoritmo si interrompe.
Complessità del caso medio è minore ma la complessità dell’algoritmo rimane O(n)
Ricerca Binaria per trovare k in una lista l.
Come funziona e che complessità ha?
Fisso indice iniziale e finale.
Analizzo l’elemento centrale.
Se k è minore allora cerco nella parte sinistra (cambiando valore finale hgh) altrimenti in quella destra se k è maggiore.
Ripeto fin quando l’elemento centrale è = k.
Complessità: log2(n)
Perchè ad ogni iterazione la lista si dimezza circa.
Caso peggiore del tempo e caso peggiore dello spazio cosa ci dicono sul costo computazionale?
caso peggiore tempo: fornisce un limite superiore alla complessità del programma.
caso peggiore dello spazio: fornisce la quantità di memoria max necessaria al programma per essere eseguito con un dato input.
Cosa è lo studio del costo sintotico?
Quando diciamo che f(n) è un O grande di g(n)?
Cosa rappresenta quindi O(g(n))
Analisi del comportamento della funzione di costo al crescere della dimensione dell’input al fine di identificare una funzione asintotica che la limiti superiormente.
Cerco la funzione più piccola che limiti superiormente la funzione di costo.
Se esistono due valori c>0 e n>n0 tali che f(n) <= c*g(n) per ogni n>n0 allora f(n) è un O grande di g(n).
O(g(n)) rappresenta tutte le funzioni il cui ordine di grandezza è minore o uguale a g(n).
Tipiche funzioni di costo
1: costante
logaritmica
n: lineare
n*log
n^k: polinomiale
k^n: esponenziale
n!: fattoriale
Ordine di complessità della ricerca sequenziale, della somma di matrici nxn, somma matrici nxm, prodotto di matrici nm e mq
n, n^2, nxm, nxmxq