Appunti completi Algoritmi e Strutture dati

Algoritmi e strutture dati: complessità computazionale

Ricerca lineare

T_b: Θ(1)
T_w: Θ(n)
T_a: Θ(n)

Ricerca dicotomica

T_b: Θ(1)
T_w: Θ(log n)
T_a: Θ(log n)

Ricerca minimo

T_w,n: Θ(n)

Selection sort

T_b(n): Θ(n²)
T_w(n): Θ(n²)
T_a(n): Θ(n²)

Insertion sort

T_b(n): Θ(n)
T_w(n): Θ(n²)
T_a(n): Θ(n²)

Inserimento in coda

T_b(n,1): Θ(1)
T_w(n,n): Θ(n)
T_a(n): Θ(n)

Bubble sort

T_b(n): Θ(n)
T_w(n): Θ(n²)
T_a(n): Θ(n²)

Merge

T_(n,m,r): Θ(n, m, r)
T_(n,n): Θ(n)

Merge sort

T_b(n): Θ(n log n)
T_w(n): Θ(n log n)
T_a(n): Θ(n log n)

Partizion

T_(n): Θ(n)

Quick sort

T_b(n): Θ(n log n)
T_w(n): Θ(n²)
T_a(n): Θ(n log n)

Ridimensionamento con espansione lineare

T_n: Θ(n)

Ridimensionamento con espansione geometrica

T_{(n,log n)}: Θ(n)

Inserimento di un elemento in lista

T_b(n): Θ(1)
T_w(n): Θ(n)
T_a(n): Θ(n)

Visita di una lista

T_b(n): Θ(n)

Ricerca di un elemento in lista

T_b(n): Θ(n)
T_w(n): Θ(n)
T_a(n): Θ(n)

Visita di un BST

T_(n): Θ(n)

Ricerca di un elemento in un BST

T_b(n,1): Θ(1)
T_w(n,n): Θ(log n)
T_a(n): Θ(log n)

Cancellazione di un elemento

T_b(n): Θ(1)
T_w(n): Θ(n)
T_a(n): Θ(n)

Ricerca di un elemento in una HT

T_b(n): Θ(1)
T_w(n): Θ(n)
T_a(n,n): Θ(1)

Inserimento di un elemento

T_b(n,1): Θ(1)
T_w(n,n): Θ(log n)
T_a(n): Θ(1)

Cancellazione di un elemento in una HT

T_b(n): Θ(1)
T_w(n): Θ(n)
T_a(n): Θ(1)

Visita di una HT

T_b(n): Θ(n)

Algoritmi e strutture dati: confronti combinatoriali

Ricerca lineare

T_b: Θ(1)
T_w: Θ(n)
T_a: Θ(n)

Ricerca dicotomica

T_b: Θ(1)
T_w: Θ(log n)
T_a: Θ(log n)

Ricerca minimo

T_m: Θ(n)
T_a: Θ(n)

Selezione sort

T_b(n): Θ(n²)
T_w(n): Θ(n²)
T_a(n): Θ(n²)

Insertion sort

T_b(n): Θ(n)
T_w(n): Θ(n²)
T_a(n): Θ(n²)

Inserimento in coda

T_b(n): Θ(1)
T_w(n): Θ(n)
T_a(n): Θ(n)

Bubble sort

T_b(n): Θ(n)
T_w(n): Θ(n²)
T_a(n): Θ(n²)

Merge

T_b(n, m): Θ(m, n, m_i)
T_w(n): Θ(n)
T_a(n): Θ(n)

Merge sort

T_b(n): Θ(n log n)
T_w(n): Θ(n log n)
T_a(n): Θ(n log n)

Partition

T_m: Θ(n)

Quick sort

T_b(n): Θ(n log n)
T_w(n): Θ(n²)
T_a(n): Θ(n log n)

Ridimensionamento con espansione lineare

T_b: Θ(n²)
T_a: Θ(n²)

Ridimensionamento con espansione geometrica

T_b: Θ(n)
T_a: Θ(n)

Vista di una lista

T_b(n): Θ(1)
T_w(n): Θ(1)
T_a(n): Θ(1)

Ricerca di un elemento in lista

T_b(n): Θ(1)
T_w(n): Θ(n)
T_a(n): Θ(n)

Cancellazione di un elemento

T_b(m): Θ(1)
T_w(n): Θ(n)
T_a(n): Θ(1)

Vista di una BST

T_b(n): Θ(n)
T_w(n): Θ(n)
T_a(n): Θ(n)

Ricerca di un elemento in BST

T_b(m): Θ(log n)
T_w(n): Θ(n)

Inserimento di un elemento