[Algoritmi, Problema] Selezione casuale di Nodi in un albero
Si ha un albero i cui nodi possono avere un numero variabile di ramificazioni.
La classe della struttura è definita in tal modo (c++):
Definire un algoritmo che non sia O(n), che, partendo dal Root (Nodo Primario), arrivi a selezionare casualmente un Nodo all'interno dell'albero, in modo che la distribuzione della probabilità (che un nodo sia scelto) sia uniforme in tutto l'albero (la probabilità totale di essere selezionato deve essere uguale per tutti i nodi), conoscendo unicamente il numero totale di nodi all'interno dell'albero. ( Naturalmente però un nodo conosce il numero dei figli diretti )
Il problema, così come è descritto, è irrisolvibile, come dimostrato da vict85.
La classe della struttura è definita in tal modo (c++):
class Node
{
public:
Node();
~Node();
private:
vector<Node*> NextNodes; //Numero variabile di figli diretti
};
Definire un algoritmo che non sia O(n), che, partendo dal Root (Nodo Primario), arrivi a selezionare casualmente un Nodo all'interno dell'albero, in modo che la distribuzione della probabilità (che un nodo sia scelto) sia uniforme in tutto l'albero (la probabilità totale di essere selezionato deve essere uguale per tutti i nodi), conoscendo unicamente il numero totale di nodi all'interno dell'albero. ( Naturalmente però un nodo conosce il numero dei figli diretti )
Il problema, così come è descritto, è irrisolvibile, come dimostrato da vict85.
Risposte
Non credo sia possibile risolverlo senza fare ricorso alla dimensione del sottoalbero e credo che dopotutto nel problema proposto da Google si desse abbastanza per scontato di avere tale informazione. In effetti, il fatto stesso di sapere il numero totale di nodi dell'albero fa pensare che tale informazione sia in qualche modo memorizzata a livello del nodo. Sono comunque curioso di vedere il metodo a cui avevi pensato. Anche se errato potrebbe comunque contenere idee a cui non avevo pensato e che potrebbero rivelarsi utili.
"apatriarca":
Non credo sia possibile risolverlo senza fare ricorso alla dimensione del sottoalbero e credo che dopotutto nel problema proposto da Google si desse abbastanza per scontato di avere tale informazione. In effetti, il fatto stesso di sapere il numero totale di nodi dell'albero fa pensare che tale informazione sia in qualche modo memorizzata a livello del nodo. Sono comunque curioso di vedere il metodo a cui avevi pensato. Anche se errato potrebbe comunque contenere idee a cui non avevo pensato e che potrebbero rivelarsi utili.
Avevo pensato questo:
Partendo dal Root, si scende scegliendo ogni volta casualmente ( con probabilità uniforme ) tra i figli del nodo corrente. I nodi che si incontrano li considero facenti parte di un insieme che li raggruppa in ordine d'arrivo: \(\left \{n\right \}_i\) ( \(n_0=Root\) ).
Noi di ogni nodo che incontriamo conosciamo univocamente:
- Il numero dei figli diretti \(N_c(n)\)
- la probabilità totale che venga scelto(che deve essere \(\frac{1}{N}\))
- la probabilità che venga raggiunto dal percorso(non che venga scelto), \(P_r(n)\), che è definita in tal modo: \[P_r(n_i)=\frac{P_r(n_{i-1})}{N_c(n_{i-1})}\]
Per ogni nodo, però, calcolo una probabilità \(P_p(n)\) che descrive la probabilità che il nodo sia scelto in quel momento. Nel caso in cui non venga scelto, il processo continua con uno dei suoi figli. Per trovare questa \(P_p(n)\) ho risolto l'equazione che descrive la probabilità totale \(P_t(n)\) (che noi conosciamo) che il nodo sia scelto:
\[P_t(n_i)=P_r(n_i)P_p(n_i)\prod_{k=0}^{i-1} (1-P_p(n_k))\]
Ciò significa semplicemente che la probabilità totale di essere scelto è uguale alla probabilità \(P_r(n)\)di essere raggiunto dal percorso, per la probabilità \(P_r(n)\) che venga scelto al momento, per la probabilità che (naturalmente) nessuno dei nodi precedenti sia stato scelto. Risolvendo l'equazione si trova che la Probabilità \(P_p(n)\) (che di fatto sceglie il nodo) è:
\[P_p(n_i)=\frac{1}{N P_r(n_i) \prod_{k=0}^{i-1} (1-P_p(n_k))}\]
Questo processo funziona per alcuni casi (ho testato), ma ce ne sono altri dove questo sistema mostra comportamenti bizzarri (ma comprensibili) se non addirittura critici, che lo rendono inutilizzabile. Ti faccio un esempio di un caso in cui funziona, uno cui mostra un comportamento "strano" e uno in cui fallisce miseramente. Consideriamo questi 3 alberi (all'interno dei nodi c'è scritta la probabilità \(P_p\)):
1) Tutto ok, funziona
2) Già nel secondo albero si nota che l'ultimo nodo ha probabilità 2. Questo perchè è talmente difficile che venga raggiunto che \(P_p\) deve essere superiore di 1, in quanto se non lo fosse, non verrebbe scelto abbastanza volte(anche se \(P_p\) fosse 1 e fosse scelto tutte le volte) da rendere omogenea la \(P_t\). Questo 2 va a significare che il nodo, nel caso fosse raggiunto, non va scelto una sola volta, ma due!
3) Qui la cosa degenera
. Il problema è che non solo abbiamo un nodo con \(P_p\) superiore a 1, ma è seguito da un altro nodo, che è irraggiungibile, in quanto il processo sarà sempre costretto a fermarsi al nodo precedente.Spero di essermi spiegato bene
Il problema è che quello che hai calcolato non è una probabilità, ma una specie di peso da dare al tuo percorso in modo che la probabilità di quel particolare nodo sia quella desiderata. Il motivo per cui nel primo caso sembra funzionare risiede nel fatto che l'albero è perfettamente bilanciato e simmetrico. La probabilità uniforme è in quel caso la probabilità corretta da usare.
"apatriarca":
Il problema è che quello che hai calcolato non è una probabilità, ma una specie di peso da dare al tuo percorso in modo che la probabilità di quel particolare nodo sia quella desiderata.
Quello che calcolo non è un peso, ma una probabilità vera e propria.
"apatriarca":
La probabilità uniforme è in quel caso la probabilità corretta da usare.
Scusa, non ho capito.
Se il tuo ragionamento fosse giusto, cosa che ovviamente non è, la probabilità che un nodo sia scelto dovrebbe essere sempre la stessa, ovvero \(1/N\). La tua non è comunque una probabilità siccome la somma delle probabilità è diversa da uno.
Il problema non può essere risolto in \(\displaystyle O(k) \), \(\displaystyle k \) profondità dell'albero, a meno di conoscere l'informazione di cui parlava apatriarca nei suoi primi messaggi. Ogni altro metodo ha bisogno di scoprire questa informazione e nel peggiore dei casi questo vuol dire una complessità \(\displaystyle O(n) \). Ho scritto \(\displaystyle O(k) \) invece che \(\displaystyle O(\log n) \) perché \(\displaystyle k \) può essere uguale a \(\displaystyle n \) se l'albero diventa una lista. Insomma è solo mediamente nell'ordine di \(\log n\).
Nota comunque che questa affermazione dipende dalla classe scelta per il tuo albero: se tu linearizzi il tuo albero in un array allora esiste un algoritmo in tempo costante per selezionare un nodo (ma ti rende altre tipologie di operazioni molto più complesse). Insomma la scelta della classe dipende fortemente da come vuoi utilizzarla.
Detto questo vorrei farti notare che la tua classe fa due cache missing ogni volta che passi da un padre ad un figlio e che potevi tranquillamente sostituire il vector con un vector eliminando un bel po' di cache missing e diminuendo notevolmente le chiamate a new.
Gli algoritmi lineari sono facili. Per esempio, una volta selezionato un ordine completo tra i nodi (insomma un ordine in cui percorrere l'albero) ti è sufficiente generare a caso un valore \(\displaystyle k \) tra \(\displaystyle 0 \) e \(\displaystyle N-1 \) e trovare il \(\displaystyle k \)-esimo elemento. Oppure percorrerlo decidendo se proseguire o meno usando un probabilità di selezionare il \(\displaystyle k \)-esimo elemento di \(\displaystyle \frac{1}{N-k} \).
È possibile creare algoritmi che percorrono l'albero in modo meno ordinato ovviamente.
Il problema non può essere risolto in \(\displaystyle O(k) \), \(\displaystyle k \) profondità dell'albero, a meno di conoscere l'informazione di cui parlava apatriarca nei suoi primi messaggi. Ogni altro metodo ha bisogno di scoprire questa informazione e nel peggiore dei casi questo vuol dire una complessità \(\displaystyle O(n) \). Ho scritto \(\displaystyle O(k) \) invece che \(\displaystyle O(\log n) \) perché \(\displaystyle k \) può essere uguale a \(\displaystyle n \) se l'albero diventa una lista. Insomma è solo mediamente nell'ordine di \(\log n\).
Nota comunque che questa affermazione dipende dalla classe scelta per il tuo albero: se tu linearizzi il tuo albero in un array allora esiste un algoritmo in tempo costante per selezionare un nodo (ma ti rende altre tipologie di operazioni molto più complesse). Insomma la scelta della classe dipende fortemente da come vuoi utilizzarla.
Detto questo vorrei farti notare che la tua classe fa due cache missing ogni volta che passi da un padre ad un figlio e che potevi tranquillamente sostituire il vector
Gli algoritmi lineari sono facili. Per esempio, una volta selezionato un ordine completo tra i nodi (insomma un ordine in cui percorrere l'albero) ti è sufficiente generare a caso un valore \(\displaystyle k \) tra \(\displaystyle 0 \) e \(\displaystyle N-1 \) e trovare il \(\displaystyle k \)-esimo elemento. Oppure percorrerlo decidendo se proseguire o meno usando un probabilità di selezionare il \(\displaystyle k \)-esimo elemento di \(\displaystyle \frac{1}{N-k} \).
È possibile creare algoritmi che percorrono l'albero in modo meno ordinato ovviamente.
"vict85":
Se il tuo ragionamento fosse giusto, cosa che ovviamente non è, la probabilità che un nodo sia scelto dovrebbe essere sempre la stessa, ovvero \(1/N\). La tua non è comunque una probabilità siccome la somma delle probabilità è diversa da uno.
Mi sa che non hai letto bene quello che ho scritto. La probabilità che mostro nei nodi non è la probabilità totale che vengano scelti (che è per tutti \(1/N\)), ma una proprietà secondaria \(P_p\) che gestisce la selezione dei nodi una volta che questi sono stati raggiunti dal processo. La somma delle proprietà totali pertanto è uguale a 1.
Una soluzione possibile ( che funzionerebbe anche non conoscendo nemmeno il numero totale dei nodi ) potrebbe essere creare un algoritmo che (partendo da 0) studi l'albero, memorizzando i percorsi e adattandosi di conseguenza... Interessante. Forse però il fatto che debba possedere una memoria statica gli impedisce di essere una valida soluzione ... secondo voi?
Sei tu che hai chiamato \(\displaystyle P_p \) come probabilità. Ma dato che è in realtà un peso chiamiamola con la \(\displaystyle w(n) \) di weight, ci sono anche fin troppe \(\displaystyle P \) nel tuo ragionamento. Il problema però è che tu poi lo usi come probabilità dato il \(\displaystyle \prod \bigl(1-w(n_k)\bigr) \). Insomma come minimo dai per scontato che si abbia \(\displaystyle 0\le w(n) \le 1 \) ed immagino che tu voglia usare proprio \(\displaystyle w(n_i) \) per selezionare o meno l'elemento. Insomma il problema è che il tuo \(\displaystyle w \) non possiede quelle proprietà. Di fatto l'intero ragionamento da quando hai introdotto quell'elemento è sbagliato ed essendo sbagliata la formula per \(\displaystyle P_t \) lo è anche tutto il resto del tuo ragionamento.
Comunque hai parlato di selezionato in quel momento e di pesi, ma non hai spiegato assolutamente l'algoritmo. Cosa succede se giungi ad un noto senza figli e non hai selezionato alcun elemento finora.
Il metodo migliore non conoscendo il numero totale di nodi consiste nel contare i nodi e poi usare un algoritmo lineare. Stai davvero tentando di trisecare un angolo, e lo fai anche andando nella direzione sbagliata: qual'è la cardinalità dei percorsi su un albero?
Comunque hai parlato di selezionato in quel momento e di pesi, ma non hai spiegato assolutamente l'algoritmo. Cosa succede se giungi ad un noto senza figli e non hai selezionato alcun elemento finora.
Il metodo migliore non conoscendo il numero totale di nodi consiste nel contare i nodi e poi usare un algoritmo lineare. Stai davvero tentando di trisecare un angolo, e lo fai anche andando nella direzione sbagliata: qual'è la cardinalità dei percorsi su un albero?
"vict85":
Sei tu che hai chiamato \(\displaystyle P_p \) come probabilità. Ma dato che è in realtà un peso chiamiamola con la \(\displaystyle w(n) \) di weight, ci sono anche fin troppe \(\displaystyle P \) nel tuo ragionamento. Il problema però è che tu poi lo usi come probabilità dato il \(\displaystyle \prod \bigl(1-w(n_k)\bigr) \). Insomma come minimo dai per scontato che si abbia \(\displaystyle 0\le w(n) \le 1 \) ed immagino che tu voglia usare proprio \(\displaystyle w(n_i) \) per selezionare o meno l'elemento. Insomma il problema è che il tuo \(\displaystyle w \) non possiede quelle proprietà. Di fatto l'intero ragionamento da quando hai introdotto quell'elemento è sbagliato ed essendo sbagliata la formula per \(\displaystyle P_t \) lo è anche tutto il resto del tuo ragionamento.
Io veramente non capisco come sia possibile che, avendo letto e capito il mio discorso, si possa dire che \(P_p\) sia un peso... I pesi nel mio discorso non c'entrano niente... A questo punto mi sa che mi sono espresso male io.
"vict85":
Comunque hai parlato di selezionato in quel momento e di pesi, ma non hai spiegato assolutamente l'algoritmo. Cosa succede se giungi ad un noto senza figli e non hai selezionato alcun elemento finora.
In questo caso dovrebbe ricominciare. Ma questo evento non è dato da un errore nel mio metodo, ma piuttosto dalle ristrettezze delle premesse. Se i nodi del percorso selezionato sono tutti molto facili da raggiungere, è naturale che non possano essere scelti tutte le volte, in quanto questo impedirebbe la omogeneità della distribuzione di probabilità.
"vict85":
Il metodo migliore non conoscendo il numero totale di nodi consiste nel contare i nodi e poi usare un algoritmo lineare.
Sì ma... in questo modo l'algoritmo non sarebbe più autosufficiente, dovrebbe appoggiarsi ad altri metodi... Non è una soluzione.
"vict85":
Stai davvero tentando di trisecare un angolo, e lo fai anche andando nella direzione sbagliata: qual'è la cardinalità dei percorsi su un albero?
Scusa, a cosa serve sapere la "cardinalità" dei percorsi?
L'unica soluzione secondo me è data dall'esternalizzazione della memoria, applicando un processo di adattamento.
La cardinalità dell'insieme dei percorsi serve per determinare la complessità del tuo algoritmo nel caso tu non sappia il numero di elementi. La mia domanda era per farti comprendere che quel pre-calcolo ha una complessità \(O(n)\) sia in tempo che in spazio. Non risulta quindi particolarmente ottimale. Inoltre a quel punto tanto varrebbe memorizzare il numero di elementi dei vari sottoalberi oppure costruire un vector di puntatori a node in modo da fare la scelta in \(O(k)\) o \(O(1)\).
Comunque se ricominci da capo allora il tuo algoritmo diventa automaticamente \(O(n)\) e non ha alcun vantaggio rispetto a metodi più semplici e della stessa complessità. Ma a parte questo il tuo modo per selezionare \(P_p\) è matematicamente sbagliato, come hai potuto notare anche tu mettendolo in pratica.
Comunque se ricominci da capo allora il tuo algoritmo diventa automaticamente \(O(n)\) e non ha alcun vantaggio rispetto a metodi più semplici e della stessa complessità. Ma a parte questo il tuo modo per selezionare \(P_p\) è matematicamente sbagliato, come hai potuto notare anche tu mettendolo in pratica.
"vict85":
La cardinalità dell'insieme dei percorsi serve per determinare la complessità del tuo algoritmo nel caso tu non sappia il numero di elementi. La mia domanda era per farti comprendere che quel pre-calcolo ha una complessità \(O(n)\) sia in tempo che in spazio. Non risulta quindi particolarmente ottimale. Inoltre a quel punto tanto varrebbe memorizzare il numero di elementi dei vari sottoalberi oppure costruire un vector di puntatori a node in modo da fare la scelta in \(O(k)\) o \(O(1)\).
Sì, effettivamente esternalizzare la memoria è un pò OP.
"vict85":
Comunque se ricominci da capo allora il tuo algoritmo diventa automaticamente \(O(n)\)
Questa affermazione è errata, in quanto non è certo che se si ripeta nel caso specifico (e raro) in cui non riesca a selezionare nessuno, sia \(O(n)\). Solo rare volte lo è, e (in teoria) ci sono probabilità minime che addirittura superi \(O(n)\). Ma complessivamente ha una complessità media molto bassa (rispetto \(O(n)\)), e per dimostrarlo ho girato una simulazione su computer che ha analizzato una gran quantità di alberi possibili, applicando il mio algoritmo e, escludendo i casi in cui il mio metodo fallisce (caso 3), la complessità media dell'algoritmo è \(\approx O( 0.18 n )\).
"vict85":
Ma a parte questo il tuo modo per selezionare \(P_p\) è matematicamente sbagliato, come hai potuto notare anche tu mettendolo in pratica.
L'aggettivo "sbagliato" è molto relativo in questo caso. La mia matematica è giusta, e anche i risultati che ottengo sono comprensibili, alcune volte possono essere "bizzarri" (ma non per questo incorretti ) in quanto rispondono alle necessità di un metodo con delle limitazioni, come si vede nel caso 2/3.
Quando si parla di complessità di un algoritmo si intende in genere la complessità del caso peggiore, spesso più facile da calcolare. La complessità media è generalmente molto più difficile da calcolare (calcolare e stimare sono due cose diverse). Ovviamente nessuno dei due valori è sufficiente per determinare l'effettiva distribuzione.
Detto questo \(O(\alpha n) = O(n)\) per ogni \(\alpha\in\mathbb{R}\) (per la definizione). Pertanto un algoritmo che abbia bisogno di visitare un decimo degli elementi avrà comunque complessità \(\displaystyle O(n) \) anche se non visita tutti gli elementi e al contempo ha complessità \(\displaystyle O(n) \) anche un algoritmo che visita ogni elemento un miliardo di volte. In questo senso mi trovo d'accordo con Sedgewick sul fatto che un'analisi completa dovrebbe tenere conto della costante e come minimo dei vari best-case, average-case e worst-case (il meglio sarebbe essere in grado di descrivere il variare della distribuzione).
Nel tuo caso però immagino che tu abbia semplicemente usato il simbolo in modo improprio affermando che per quel particolare \(\displaystyle N \) ci vogliono \(0.174 N\) operazioni. Una informazione piuttosto inutile, insomma se la costante rimane tale al variare di \(\displaystyle N \) allora si parla di complessità lineare, se cambia in altro modo allora si parlerà di logaritmica o persino esponenziale (insomma si potrebbe avere una complessità esponenziale con una costante molto bassa). Inoltre avresti dovuto metterlo a confronto anche con la profondità dell'albero.
In ogni caso il tuo ragionamento è sbagliato, non c'è alcuna relatività in questo. Il fatto che funzioni in alcuni casi non è dimostrazione del fatto che il tuo calcolo sia giusto per quei casi, ma semplicemente del fatto che il caso in questione ha caratteristiche tali da coprire il tuo errore.
Il tuo problema, dal punto di vista computazionale, è equivalente a fare una ricerca in un albero non ordinato. Che a sua volta è sostanzialmente equivalente a farla su un array non ordinato. Provo a dare un abbozzo di dimostrazione.
Ogni algoritmo corretto deve testare un elemento alla volta. Non è possibile sapere quanti elementi precedono o seguono un particolare nodo in alcun ordinamento senza aver prima incontrato ogni elemento precedente (questa è una ipotesi implicita nel problema), pertanto non è possibile stabilire in tempo sublineare il costo dell'esclusione degli elementi che precedono o seguono un particolare nodo rispetto ad un particolare ordine. Un algoritmo efficiente testa ogni elemento al massimo una volta, ed esclude quindi gli elementi seguendo un particolare ordine. Per il punto precedente non è possibile saltare alcun elemento perché non è possibile determinare la probabilità di non incontrare l'elemento in questione. L'\(\displaystyle i \)-esimo elemento testato ha probabilità \(\displaystyle \frac{1}{N-i} \) di essere quello giusto (la probabilità è condizionata al fatto che abbiamo eliminato gli elementi precedenti[nota]La probabilità condizionata in questione è tutto ciò che sappiamo al tempo \(\displaystyle i \).[/nota]). A questo punto il valore atteso della complessità è \(\displaystyle \mathbb{E}C = \sum_{i=0}^{N-1} \frac{i+1}{N-i}\Bigl( \prod_{j=0}^{i-1}\frac{N-j-1}{N-j} \Bigr) = \sum_{i=0}^{N-1} \frac{i+1}{N} = \frac{N+1}{2} \) . Ovvero ogni soluzione del tuo problema possiede quella complessità media (ovvero è lineare sia in media che nel caso peggiore).
Detto questo \(O(\alpha n) = O(n)\) per ogni \(\alpha\in\mathbb{R}\) (per la definizione). Pertanto un algoritmo che abbia bisogno di visitare un decimo degli elementi avrà comunque complessità \(\displaystyle O(n) \) anche se non visita tutti gli elementi e al contempo ha complessità \(\displaystyle O(n) \) anche un algoritmo che visita ogni elemento un miliardo di volte. In questo senso mi trovo d'accordo con Sedgewick sul fatto che un'analisi completa dovrebbe tenere conto della costante e come minimo dei vari best-case, average-case e worst-case (il meglio sarebbe essere in grado di descrivere il variare della distribuzione).
Nel tuo caso però immagino che tu abbia semplicemente usato il simbolo in modo improprio affermando che per quel particolare \(\displaystyle N \) ci vogliono \(0.174 N\) operazioni. Una informazione piuttosto inutile, insomma se la costante rimane tale al variare di \(\displaystyle N \) allora si parla di complessità lineare, se cambia in altro modo allora si parlerà di logaritmica o persino esponenziale (insomma si potrebbe avere una complessità esponenziale con una costante molto bassa). Inoltre avresti dovuto metterlo a confronto anche con la profondità dell'albero.
In ogni caso il tuo ragionamento è sbagliato, non c'è alcuna relatività in questo. Il fatto che funzioni in alcuni casi non è dimostrazione del fatto che il tuo calcolo sia giusto per quei casi, ma semplicemente del fatto che il caso in questione ha caratteristiche tali da coprire il tuo errore.
Il tuo problema, dal punto di vista computazionale, è equivalente a fare una ricerca in un albero non ordinato. Che a sua volta è sostanzialmente equivalente a farla su un array non ordinato. Provo a dare un abbozzo di dimostrazione.
Ogni algoritmo corretto deve testare un elemento alla volta. Non è possibile sapere quanti elementi precedono o seguono un particolare nodo in alcun ordinamento senza aver prima incontrato ogni elemento precedente (questa è una ipotesi implicita nel problema), pertanto non è possibile stabilire in tempo sublineare il costo dell'esclusione degli elementi che precedono o seguono un particolare nodo rispetto ad un particolare ordine. Un algoritmo efficiente testa ogni elemento al massimo una volta, ed esclude quindi gli elementi seguendo un particolare ordine. Per il punto precedente non è possibile saltare alcun elemento perché non è possibile determinare la probabilità di non incontrare l'elemento in questione. L'\(\displaystyle i \)-esimo elemento testato ha probabilità \(\displaystyle \frac{1}{N-i} \) di essere quello giusto (la probabilità è condizionata al fatto che abbiamo eliminato gli elementi precedenti[nota]La probabilità condizionata in questione è tutto ciò che sappiamo al tempo \(\displaystyle i \).[/nota]). A questo punto il valore atteso della complessità è \(\displaystyle \mathbb{E}C = \sum_{i=0}^{N-1} \frac{i+1}{N-i}\Bigl( \prod_{j=0}^{i-1}\frac{N-j-1}{N-j} \Bigr) = \sum_{i=0}^{N-1} \frac{i+1}{N} = \frac{N+1}{2} \) . Ovvero ogni soluzione del tuo problema possiede quella complessità media (ovvero è lineare sia in media che nel caso peggiore).
"vict85":
Quando si parla di complessità di un algoritmo si intende in genere la complessità del caso peggiore, spesso più facile da calcolare. La complessità media è generalmente molto più difficile da calcolare (calcolare e stimare sono due cose diverse). Ovviamente nessuno dei due valori è sufficiente per determinare l'effettiva distribuzione.
Detto questo \(O(\alpha n) = O(n)\) per ogni \(\alpha\in\mathbb{R}\) (per la definizione). Pertanto un algoritmo che abbia bisogno di visitare un decimo degli elementi avrà comunque complessità \(\displaystyle O(n) \) anche se non visita tutti gli elementi e al contempo ha complessità \(\displaystyle O(n) \) anche un algoritmo che visita ogni elemento un miliardo di volte. In questo senso mi trovo d'accordo con Sedgewick sul fatto che un'analisi completa dovrebbe tenere conto della costante e come minimo dei vari best-case, average-case e worst-case (il meglio sarebbe essere in grado di descrivere il variare della distribuzione).
Nel tuo caso però immagino che tu abbia semplicemente usato il simbolo in modo improprio affermando che per quel particolare \(\displaystyle N \) ci vogliono \(0.174 N\) operazioni. Una informazione piuttosto inutile, insomma se la costante rimane tale al variare di \(\displaystyle N \) allora si parla di complessità lineare, se cambia in altro modo allora si parlerà di logaritmica o persino esponenziale (insomma si potrebbe avere una complessità esponenziale con una costante molto bassa). Inoltre avresti dovuto metterlo a confronto anche con la profondità dell'albero.
Sono ignorante nel campo della complessità computazionle, e dai post precedenti pensavo di aver capito (erroneamente) che la complessità dell'algoritmo fosse banalmente il numero di Nodi che l'algoritmo testava.
"vict85":
In ogni caso il tuo ragionamento è sbagliato, non c'è alcuna relatività in questo. Il fatto che funzioni in alcuni casi non è dimostrazione del fatto che il tuo calcolo sia giusto per quei casi, ma semplicemente del fatto che il caso in questione ha caratteristiche tali da coprire il tuo errore.
Chiamami testardo... ma continuo ad avere l'impressione che arrivi a questa conclusione guardando solo il risultato pratico.
"vict85":
Il tuo problema, dal punto di vista computazionale, è equivalente a fare una ricerca in un albero non ordinato. Che a sua volta è sostanzialmente equivalente a farla su un array non ordinato. Provo a dare un abbozzo di dimostrazione.
Ogni algoritmo corretto deve testare un elemento alla volta. Non è possibile sapere quanti elementi precedono o seguono un particolare nodo in alcun ordinamento senza aver prima incontrato ogni elemento precedente (questa è una ipotesi implicita nel problema), pertanto non è possibile stabilire in tempo sublineare il costo dell'esclusione degli elementi che precedono o seguono un particolare nodo rispetto ad un particolare ordine. Un algoritmo efficiente testa ogni elemento al massimo una volta, ed esclude quindi gli elementi seguendo un particolare ordine. Per il punto precedente non è possibile saltare alcun elemento perché non è possibile determinare la probabilità di non incontrare l'elemento in questione. L'\(\displaystyle i \)-esimo elemento testato ha probabilità \(\displaystyle \frac{1}{N-i} \) di essere quello giusto (la probabilità è condizionata al fatto che abbiamo eliminato gli elementi precedenti. A questo punto il valore atteso della complessità è \(\displaystyle \mathbb{E}C = \sum_{i=0}^{N-1} \frac{i+1}{N-i}\Bigl( \prod_{j=0}^{i-1}\frac{N-j-1}{N-j} \Bigr) = \sum_{i=0}^{N-1} \frac{i+1}{N} = \frac{N+1}{2} \) . Ovvero ogni soluzione del tuo problema possiede quella complessità media (ovvero è lineare sia in media che nel caso peggiore).
Ho capito fino a quando applichi quella formula per calcolare la complessità media, ma mi fido del risultato.
Ok... Quindi possiamo affermare che così come è descritto il problema è irrisolvibile con una complessità minore di \(O(n)\). Però tentare di risolverlo e discuterne con voi è stato veramente interessante!
Grazie a tutti.
Il risultato è piuttosto semplice da calcolare in realtà. Porti il denominatore fuori dalla somma, usi la formula per i numeri triangolari e poi semplifichi.
Per la semplificazione precedente ho moltiplicato la probabilità condizionata per la probabilità dell'evento su chi sto condizionando trovando la probabilità dell'intersezione dei due eventi.
Nel caso non si sappia la dimensione penso che si possa fare in esattamente n test (il numero di operazioni è superiore ma poco importante). Dovrei controllare se tutto va bene ma penso che questo funzioni:
1) seleziono il root
2) proseguo nell'ordine scelto e cambio selezione con il nuovo elemento con probabilità 1/2
3) prendo un nuovo nodo e cambio selezione con probabilità 1/3 e così via.
Per la semplificazione precedente ho moltiplicato la probabilità condizionata per la probabilità dell'evento su chi sto condizionando trovando la probabilità dell'intersezione dei due eventi.
Nel caso non si sappia la dimensione penso che si possa fare in esattamente n test (il numero di operazioni è superiore ma poco importante). Dovrei controllare se tutto va bene ma penso che questo funzioni:
1) seleziono il root
2) proseguo nell'ordine scelto e cambio selezione con il nuovo elemento con probabilità 1/2
3) prendo un nuovo nodo e cambio selezione con probabilità 1/3 e così via.
"vict85":
Il risultato è piuttosto semplice da calcolare in realtà. Porti il denominatore fuori dalla somma, usi la formula per i numeri triangolari e poi semplifichi.
Per la semplificazione precedente ho moltiplicato la probabilità condizionata per la probabilità dell'evento su chi sto condizionando trovando la probabilità dell'intersezione dei due eventi.
aaaah, ok. Adesso ho capito tutto. Grazie
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo