Domanda sulla complessità temporale
Salve a tutti,vi ringrazio in anticipo per il tempo che dedicherete a leggere questo post.
Veniamo al dunque: stavo leggendo questa pagina di wikipedia (https://it.wikipedia.org/wiki/Complessi ... _temporale) premetto che dell argomento non conosco niente ma ne sono incuriosito, volevo chiedervi se dovessi scrivere un algoritmo per calcolare $ x $ in $ n^x=y $ avendo noti $ n $ e $ y $ in che parte della tabella (presente nella pagina che ho indicato) si collocherebbe? grazie in anticipo
Veniamo al dunque: stavo leggendo questa pagina di wikipedia (https://it.wikipedia.org/wiki/Complessi ... _temporale) premetto che dell argomento non conosco niente ma ne sono incuriosito, volevo chiedervi se dovessi scrivere un algoritmo per calcolare $ x $ in $ n^x=y $ avendo noti $ n $ e $ y $ in che parte della tabella (presente nella pagina che ho indicato) si collocherebbe? grazie in anticipo
Risposte
non riesco a caire cosa intendi, ma mi sembra che tu abbia frainteso il discorso.
Prima di tutto non si parla di formule, ma di algoritmi, di "passaggi" attraverso i quali raggiungi il risultato.
facciamo un'esempio: voglio sapere la complessità dell'algoritmo che mi permette di controllare quali elementi del vettore a sono contenuti anche nel vettore b.
immagino un algoritmo
questo codice prende il primo elemento di a e lo confronta con tutti gli elementi di b,
poi prende il secondo elemento di a e lo confronta con tutti gli elementi di b,
....fino all'ultimo elemento di a.
quindi alla fine scorri tutti gli elementi di b per n volte, cioè per il numero di elementi di a.
quindi alla fine questa operazione mi costa m*n con m e n dimensione dei due vettori.
immaginando che le dimensioni di a e b siano circa uguali posso dire che m*n è approssimabile con un $n^2$.
in realtà il discorso della complessità è un pò più lungo, la complessità può essere scritta in funzione di O(o grande), di o(o piccolo) e di omega, però bisogna capire prima il tuo livello di conoscenza dell'informatica, perché è quasi impossibile da spiegare senza fare esempi
Prima di tutto non si parla di formule, ma di algoritmi, di "passaggi" attraverso i quali raggiungi il risultato.
facciamo un'esempio: voglio sapere la complessità dell'algoritmo che mi permette di controllare quali elementi del vettore a sono contenuti anche nel vettore b.
immagino un algoritmo
for(i=0;i<n;i++){
for(j=0;j<m;j++){
if(a[i]=b[j])
printf(a[i])
}
}
questo codice prende il primo elemento di a e lo confronta con tutti gli elementi di b,
poi prende il secondo elemento di a e lo confronta con tutti gli elementi di b,
....fino all'ultimo elemento di a.
quindi alla fine scorri tutti gli elementi di b per n volte, cioè per il numero di elementi di a.
quindi alla fine questa operazione mi costa m*n con m e n dimensione dei due vettori.
immaginando che le dimensioni di a e b siano circa uguali posso dire che m*n è approssimabile con un $n^2$.
in realtà il discorso della complessità è un pò più lungo, la complessità può essere scritta in funzione di O(o grande), di o(o piccolo) e di omega, però bisogna capire prima il tuo livello di conoscenza dell'informatica, perché è quasi impossibile da spiegare senza fare esempi
Ciao mi scuso per non aver risposto prima ma sono stato molto impegnato a causa di esigenze lavorative che mi vedono molto impegnato sul posto di lavoro.Le mie conoscenze informatiche sono molto scarse,comunque l'esempio che hai fatto penso di averlo capito.Se puoi farmi esempi inerenti a un possibile algoritmo per trovare una soluzione all'equazione che ho postato te ne sarei grato.grazie acora
Direi che è semplicemente:
x = log(y)/log(n);
$n^x=y$ se vuoi trovare x devi fare logaritmo in base n di y, che può essere calcolato come ha detto apatriarca,...però questa è una formula risolutiva, non è un algoritmo.
Poi non hai specificato cosa sono y ed n se sono variabili "scalari" è una singola operazione, se sono vettori e devi calcolarlo solo tra gli elementi x[0] e y[0], x[1] e y[1],... allora è un O(d)con d =dimensione dei vettori.
se ti serve vedere anche le coppie di valori "misti", cioè
x[0] e y[0],
x[0] e y[1],
x[1] e y[0],
x[1] e y[1],...
allora inizia ad essere un O($d^2$)...
https://it.wikibooks.org/wiki/Algoritmi/L%27analisi_di_complessità_degli_algoritmi
qui spiega la differenza tra algoritmi di ricerca, lineare(scandisci tutto l'elenco finchè non trovi quello che cerchi) o dicotomica(se assumi la lista ordinata guardi l'elemento centrale, e guardi se quello che cerchi è prima o dopo l'elemento centrale. se vedi che , per esempio, è dopo, cerchi l'elemento centrale della seconda metà e continui così).
immagina di cercare una parola nel dizionario, la ricerca lineare significa che tu sfogli dalla prima pagina fino all'ultima per cercare la parola, la ricerca dicotomica invece la fai aprendo il dizionario a metà, poi guardi se la parola che cerchi è prima o dopo la pagina che hai trovato, quindi apri a metà della metà delle pagine precedenti o di quelle successive, e così via.
quello che voglio farti capire è che l'analisi della complessità ha senso se guardi diversi algoritmi che fanno la medesima cosa(una ricerca) ma in modo diverso.
se ti va di approfondire ci dovrebbero essere delle slide di corsi di algoritmi e programmazione del PoliMi o del PoliTo in cui si trattano alcuni algoritmi di ricerca e di ordinamento analizzandone la complessità
Poi non hai specificato cosa sono y ed n se sono variabili "scalari" è una singola operazione, se sono vettori e devi calcolarlo solo tra gli elementi x[0] e y[0], x[1] e y[1],... allora è un O(d)con d =dimensione dei vettori.
se ti serve vedere anche le coppie di valori "misti", cioè
x[0] e y[0],
x[0] e y[1],
x[1] e y[0],
x[1] e y[1],...
allora inizia ad essere un O($d^2$)...
https://it.wikibooks.org/wiki/Algoritmi/L%27analisi_di_complessità_degli_algoritmi
qui spiega la differenza tra algoritmi di ricerca, lineare(scandisci tutto l'elenco finchè non trovi quello che cerchi) o dicotomica(se assumi la lista ordinata guardi l'elemento centrale, e guardi se quello che cerchi è prima o dopo l'elemento centrale. se vedi che , per esempio, è dopo, cerchi l'elemento centrale della seconda metà e continui così).
immagina di cercare una parola nel dizionario, la ricerca lineare significa che tu sfogli dalla prima pagina fino all'ultima per cercare la parola, la ricerca dicotomica invece la fai aprendo il dizionario a metà, poi guardi se la parola che cerchi è prima o dopo la pagina che hai trovato, quindi apri a metà della metà delle pagine precedenti o di quelle successive, e così via.
quello che voglio farti capire è che l'analisi della complessità ha senso se guardi diversi algoritmi che fanno la medesima cosa(una ricerca) ma in modo diverso.
se ti va di approfondire ci dovrebbero essere delle slide di corsi di algoritmi e programmazione del PoliMi o del PoliTo in cui si trattano alcuni algoritmi di ricerca e di ordinamento analizzandone la complessità
Ringrazio entrambi in particolare insideworld per la risposta esaustiva e per avermi indirizzato verso la ricerca di materiale interessante.grazie ancora
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo