Merge Sort

Algoritmo intuitivo e ottimo.
Utilizza l’algoritmo di fusione di sottosequenze ordinate.

La chiamata chiede di ordinare l’array dal primo, 1, all’ultimo, N, elemento.
A ogni chiamata, dopo aver calcolato Medio, si effettuano due chiamate ricorsive, da Inf a Medio e da Medio+1 a Sup.

In pratica le chiamate ricorsive scendono fino al livello di array con un solo elemento.
Al ritorno di ogni coppia di chiamate si effettua la fusione, merge, delle due parti ordinate (l’array con un solo elemento è già ordinato…).

ms1Esempio 1

Sia v={1, 3, 7, 4, 15, 0, 9, 10}

Le chiamate ricorsive sugli indici da 1 a 8 e con i valori medi successivi

  • (1+8)/2 = 4
  • (1+4)/2 = 2
  • (5+8)/2 = 6
  • (1+2)/2 = 1
  • (3+4)/2 = 3
  • (5+6)/2 = 5
  • (7+8)/2 = 7

hanno l’effetto di raggiungere i singoli elementi.

Con i valori effettivi, l’array dopo le chiamate ricorsive diventa una sequenza di 8 array con un elemento

ms11

Al ritorno di ogni due chiamate ricorsive avviene la fusione di due array ordinati…

ms12

ms2Esempio 2

Sia v={1, 3, 7, 4, 15, 0, 9, 10, 8, 2}

Le chiamate ricorsive sugli indici da 1 a 10 raggiungono i singoli elementi con 2 passaggi in più…

  • (1+10)/2 = 5
  • (1+5)/2 = 3
  • (6+10)/2 = 8
  • (1+3)/2 = 2
  • (4+5)/2 = 4
  • (6+8)/2 = 7
  • (9+10)/2 = 9
  • (1+2)/2 = 1
  • (6+7)/2 = 6.
Considerando i valori effettivi dell’array e l’esecuzione di tutti i passi…
ms22

Numeri di Fibonacci

Vedi la discussione


Esercizi

  1. Calcola la somma dei primi n numeri di Fibonacci.
    Visualizza i passi compiuti con una tabella per n da 1 a

    n f(n) Somma
    1 1 1
    2 1 2
    3 2 4
    4 3 7
    5 5 12
    6 8 20
  2. Quanto vale il rapporto tra due numeri di Fibonacci consecutivi?
    Prova per n crescente finché non raggiungi un’approssimazione adeguata

    n f(n) (n+1)°/n° n°/(n+1)°
    1 1
    1 1 1 1
    2 1 2 0,5
    3 2 1,5 0,6…
    4 3 1,6… 0,625
    5 5 1,625 0,6153…
    1,6180339… 0,6180339…

Complessità degli algoritmi

Dopo aver analizzato il problema e individuati i 3 algoritmi discutiamo la loro complessità in tempo.

Algoritmo ricorsivo: il tempo di attesa può essere considerato proporzionale al numero di chiamate ricorsive

  • T(1) = 1
  • T(2) = 1
  • T(3) = 1+T(2)+T(1) = 1+1+1 = 3 > 22-1
  • T(4) = 1+T(3)+T(2) = 1+3+1 = 5 > 22-1
  • T(5) = 1+T(4)+T(3) = 1+5+3 = 9 > 23-1
  • T(6) = 1+T(5)+T(4) = 1+9+5 = 15 > 23-1
  • T(7) = 1+T(6)+T(5) = 1+15+9 = 25 > 24-1
  • T(8) = 1+T(7)+T(6) = 1+25+15 = 41 > 24-1
  • T(n) ≥ 2n/2-1.

Il tempo di attesa è maggiore di un tempo esponenziale, anche se con esponente n/2 piuttosto che n, quindi per n molto grande

T(n) ∈ O(2n).

L’algoritmo ricorsivo per il calcolo dell’n-simo numero di Fibonacci ha complessità esponenziale!

Algoritmo iterativo: si tratta di un algoritmo con un’iterazione semplice, senza chiamate ricorsive, quindi

  • T(n)=c1+c2n
  • T(n) ∈ O(n).

L’algoritmo iterativo per il calcolo dell’n-simo numero di Fibonacci ha complessità lineare!

Con formula: se consideriamo costante il tempo necessario per svolgere le singole operazioni presenti nella formula allora

  • T(n)=c
  • T(n) ∈ O(1).

Se consideriamo che per n molto grande l’operazione di elevamento a potenza potrebbe dipendere dal numero di cifre e che il numero di cifre del risultato cresce proporzionalmente al log di n allora si ottiene una complessità O(log n).

Conclusioni: per il calcolo dell’n-esimo numero di Fibonacci esistono diversi algoritmi con complessità diverse. Al variare di n utilizzeremo l’algoritmo più conveniente!