Algoritmi e Strutture Dati

Algoritmi e strutture dati: lezione n° 1

Introduzione

Al Khwarizmi: Algoritmi (matematico persiano)
Knuth: Calcolo delle complessità degli algoritmi

Principio di "inclusione aritmetica"

a pessi: somma stia da 1 ad n

Logaritmi

Proprietà: b = base (essenzialmente x ed n numeri)
Proprietà del cambiamento di base del Logaritmo: Con a > 0 e a ≠ ±1, dato che a al denominatore, poss. dire in anke il suo reciproco è una costante

Andamento delle funzioni

Input: [Andamento delle funzioni]
n³ log₂ (n)
n³: Nota! Il logaritmo moltiplicato per n³ sta sotto appunto ad n³ come per gli altri casi.

Big-O complexity chart

1. O(log₂ n): funzione logaritmica
2. O(n): funzione identità
3. O(n log₂ n): funzione logaritmica con costante
4. O(n²): funzione quadratica
5. O(2ⁿ): funzione esponenziale
6. O(n!): funzione fattoriale

Passo "induttivo": esempio

S_n = ∑_K=1ⁿ K = ^{n (n + 1)}/₂ ∀ n ≥ ⊕
Parto dalla definizione della cosa, che fare riferimento alla definizione della proprietà che voglio verificare; in questo caso fare riferimento alla definizione di sommatoria; Devo quindi verificare inserendo un "input", c:∑_K=1ⁿK = ^{1(n + 1)}/₂1 = ¹⁽²⁾/₂1 = ²/₂1 = 1

Ora devo fare il "passo induttivo" con una sorta di "atto di fede": ⊕_i=1ⁿ i = ^{n (n + 1)}/₂ devo dimostrare che ∑_i=1ⁿ⁺¹ i = ^{(n + 1)((n + 1) + 1)}/₂ per "potere induttivo" deve essere uguale a (⊕_i=1ⁿ i) + (n + 1) = ^{n (n + 1)}/₂ + (n + 1)

Quindi: (n + 1) (n + 2) ———————?2n (n + 1) ————— + (n + 1)2 fatto comunen (n + 1) + 2 (n + 1) ———————————2(n + 1) (n + 2) ————————2

Dato che ottengo lo stesso risultato, il "gioco" è stato verificato e quindi abbiamo dimostrato che _{∀n ≥ 1 n} ^Σ_K=1 k = ^{n (n + 1)}————————————————2 grazie al passo induttivo.

DeleteMax per code di priorità con heap

1. Prendere l'elemento più a destra dell'ultimo livello e lo scambio con la radice (che se ne va).
2. Scegliere la chiave minore tra quelle dei due figli. Nb. Gli elementi nell'ultimo livello vanno a sinistra dell'heap binario!

Risultato finale: La complessità di una cola heap è log₂ n. Ho terminato i punti per ricordare che in pratica ne facciamo n-1. Posso mettere una annotazione provvisoria per il punto 2. H (log₂ n) Popnu H (log₂ n)

Esempio di carta di heap binario

funct Max : Chart rest thurs il puntatore alla radice
insertElem ("qualcosa", 230, pq)

Metodo alle tre

Questa è la cosa peggiore H(log₂ n)# op -> tante quanto il n° ott e velli
Il caso migliore invece n ha nel caso, usano i modi che nel fra l’adiavi e del podore
insertElem ("qualcosa", 300, pq)

1^o passo 3, 1   Si confronta il 400 con i due figli e si sceglie quello con chiave minore

Risultato finale: