Discussioni su argomenti di Informatica
05/07/2023, 11:34
Sia $n$ la dimensione della struttura dati in ingresso all'algoritmo Quicksort. Il caso peggiore (che capita quando il partizionamento produce due sottostrutture completamente sbilanciate, ossia una con nessun elemento e un'altra con $n-1$ elementi) si può descrivere con la ricorrenza
$T(n) = T(0) + T(n-1) + \Theta(n) = T(n-1) + \Theta(n)$.
Si vuole dimostrare che $T(n) = \Theta(n^2)$ utilizzando il metodo di sostituzione.
Per fare questo, è necessario dimostrare (sempre tramite tale metodo) che $T(n) = O(n^2)$ e $T(n) = \Omega(n^2)$.
La dimostrazione per il primo caso, con l'utilizzo della definizione di O-grande, è riportata come segue
$T(n) \leq c(n - 1)^2 + \Theta(n) = cn^2 - 2cn + c + \Theta(n) \leq cn^2$.
L'ultima maggiorazione è giustificata dicendo che "si sceglie un $c$ sufficientemente grande per cui il termine $-2cn + c$ supera $\Theta(n)$". Come dimostro matematicamente che effettivamente esiste un tale $c_0$ sufficientemente grande per cui si verifica quanto detto?
05/07/2023, 14:22
Qual'è il significato di \(\Theta(n)\)? Nota che possiamo scegliere il valore di \(c\) a piacere in quanto le relazioni rimangono certamente valide prendendo un \(c\) più grande. Hai che \(\Theta(n)\) è più piccolo di un qualche \(dn\) e quindi sceglierai \(c\) in modo che \(d - 2c\) è negativo e consideri un \(n\) abbastanza grande per cui \((2c - d)n > c\).
07/07/2023, 08:59
Dunque, se ho ben capito, tu hai scelto una delle possibili funzioni lineari dall'insieme $\Theta(n)$, ponendo dunque $\Theta(n) = dn, d > 0$. Quindi la relazione finale diventa
$ cn^2 - 2cn + c + dn \leq cn^2 $
$ -2cn + c + dn \leq 0 $
$ (2c - d)n \geq c $
Qui bisogna necessariamente imporre che la quantità $(2c - d)$ sia positiva.
Volendo invece dimostrare anche che $T(n) = \Omega(n^2)$, usando la definizione ottengo che
$ T(n) \geq c(n - 1)^2 + \Theta(n) = cn^2 - 2cn + c + dn$
Dunque, seguendo lo stesso procedimento di prima, impongo che
$cn^2 - 2cn + c + dn \geq cn^2$
$-2cn + c + dn \geq 0$
$ (2c - d)n \leq c $
Ora, a primo membro ho la quantità $(2c - d)$ che può essere di qualunque segno, mentre $n$ è positivo; quindi il segno a primo membro è quello di $(2c - d)$; a secondo membro ho $c$ che è positiva e il segno di disuguaglianza è $\leq$. Dunque, a primo membro posso avere sia un numero negativo (che è certamente minore di una quantità positiva) che un numero positivo (purchè sia $\leq c$), quindi posso sia imporre che $(2c - d) < 0$ che $(2c - d) > 0$?
07/07/2023, 13:58
Devi utilizzare dei \(c\) e \(d\) diversi nelle due dimostrazioni.
07/07/2023, 18:26
Grazie.
Skuola.net News è una testata giornalistica iscritta al Registro degli Operatori della Comunicazione.
Registrazione: n° 20792 del 23/12/2010.
©2000—
Skuola Network s.r.l. Tutti i diritti riservati. — P.I. 10404470014.