[Ordini di grandezza delle funzioni]
ciao a tutti 
!!! sto facendo un'esercizio che richiede di ordinare, in ordine crescente, una serie di funzioni. Volevo sapere se il ragionamento che ho adottato va bene e se qualcuno, per favore, mi può consigliare delle dispense sull'argomento e più in generale sulla complessità degli algoritmi.
Le funzioni da ordinare sono le seguenti:
\(\displaystyle f_1(n)=4^{log_4log_{16}^4n} ;
f_2(n)=16^{log_4log_{16}^4n} ;
f_3(n)=2^{log_4n}
\)
Ho iniziato con \(\displaystyle f_1(n)=4^{log_4log_{16}^4n}\) applicando la seguente proprietà:
\(\displaystyle a^{log_bc}=c^{log_ba} \) con \(\displaystyle a , b \) e \(\displaystyle c \) appartenenti a \(\displaystyle N \) e \(\displaystyle b>1 \)
ottenendo:
\(\displaystyle 4^{log_4log_{16}^4n}=log_{16}^4n^{log_44}=log_{16}^4n^1=log_{16}^4n=O(n^4)\)
il mio problema è \(\displaystyle log_{16}^4n \) ovvero l'esponente \(\displaystyle 4 \) del logaritmo, non ho capito come va applicato,
è corretto l'ordine \(\displaystyle O(n^4) \) ??
!!! sto facendo un'esercizio che richiede di ordinare, in ordine crescente, una serie di funzioni. Volevo sapere se il ragionamento che ho adottato va bene e se qualcuno, per favore, mi può consigliare delle dispense sull'argomento e più in generale sulla complessità degli algoritmi.Le funzioni da ordinare sono le seguenti:
\(\displaystyle f_1(n)=4^{log_4log_{16}^4n} ;
f_2(n)=16^{log_4log_{16}^4n} ;
f_3(n)=2^{log_4n}
\)
Ho iniziato con \(\displaystyle f_1(n)=4^{log_4log_{16}^4n}\) applicando la seguente proprietà:
\(\displaystyle a^{log_bc}=c^{log_ba} \) con \(\displaystyle a , b \) e \(\displaystyle c \) appartenenti a \(\displaystyle N \) e \(\displaystyle b>1 \)
ottenendo:
\(\displaystyle 4^{log_4log_{16}^4n}=log_{16}^4n^{log_44}=log_{16}^4n^1=log_{16}^4n=O(n^4)\)
il mio problema è \(\displaystyle log_{16}^4n \) ovvero l'esponente \(\displaystyle 4 \) del logaritmo, non ho capito come va applicato,
è corretto l'ordine \(\displaystyle O(n^4) \) ??
Risposte
Ma scusa tanto:
\[
4^{\log_4 (\log_{16}^4 n)} = \log_{16}^4 n = \left( \frac{\log n}{\log 16}\right)^4 = \text{O}\left( \log^4 n\right)\; ,
\]
no?
\[
4^{\log_4 (\log_{16}^4 n)} = \log_{16}^4 n = \left( \frac{\log n}{\log 16}\right)^4 = \text{O}\left( \log^4 n\right)\; ,
\]
no?
ah! ecco! praticamente ho sbagliato tutto!! 
come mai viene "trasformata" così??
come mai viene "trasformata" così??
Definizione di logaritmo e cambiamento di base.
allora anche \(\displaystyle 16^{log_4log_{16}^4n}=16^{log_4(logn/log16)^4}=(log_2n/log_216)^4=(log_2n/4)^4=O(log_2^4n) \) ??
ho svolto anche questa \(\displaystyle 2^{log_4n}=n^{log_42} =n^{1/2}=√n=O(√n)\), va bene??
Scusa, ma dato che \(16=4^2\), per le proprietà delle potenze e quelle (già richiamate) dei logaritmi hai:
\[
\begin{split}
16^{\log_4 (\log_{16}^4 n)} &= (4^2)^{\log_4 (\log_{16}^4 n)} \\
&= (4^{\log_4 (\log_{16}^4 n)})^2 \\
&= (\log_{16}^4 n)^2 \\
&= \log_{16}^8 n \\
&= \frac{1}{\log^8 16}\ \log^8 n
\end{split}
\]
quindi \(16^{\log_4 (\log_{16}^4 n)} = \Theta( \log^8 n)\) (in cui il simbolo \(x(n)=\Theta( a(x))\) denota il fatto che \(x(n)\) è contemporaneamente \(\text{O}(a(n))\) e \(\Omega (a(n))\)).
\[
\begin{split}
16^{\log_4 (\log_{16}^4 n)} &= (4^2)^{\log_4 (\log_{16}^4 n)} \\
&= (4^{\log_4 (\log_{16}^4 n)})^2 \\
&= (\log_{16}^4 n)^2 \\
&= \log_{16}^8 n \\
&= \frac{1}{\log^8 16}\ \log^8 n
\end{split}
\]
quindi \(16^{\log_4 (\log_{16}^4 n)} = \Theta( \log^8 n)\) (in cui il simbolo \(x(n)=\Theta( a(x))\) denota il fatto che \(x(n)\) è contemporaneamente \(\text{O}(a(n))\) e \(\Omega (a(n))\)).
ok!! allora riguardo le proprietà di ambedue gli argomenti e faccio un po' di esercizi. Dove posso trovare materiale didattico riguardo la complessità computazionale?? grazie mille!!
Beh, fin qui non si tratta di complessità, ma proprio delle proprietà base delle potenze e dei logaritmi.
Per il resto, non sò: probabilmente ti potrebbe bastare qualche buon libro di Matematica Discreta, tipo il Graham, Knuth & Patashnik, Matematica Discreta.
Per il resto, non sò: probabilmente ti potrebbe bastare qualche buon libro di Matematica Discreta, tipo il Graham, Knuth & Patashnik, Matematica Discreta.
di matematica discreta già ce l'ho, ne ho due, nello specifico: uno della exprofessoressa di discreta( ma è del tutto inutile, pieno di errori non solo sugli esercizi ma anche grammaticali, e il modo in cui esprime i concetti è patetico) l'altro è fatto meglio e tratta anche di complessità , ma non approfondisce l'argomento; ho anche lo knuth concrete mathematics e ho il cormen introduzione a gli algoritmi e strutture dati sul quale studio..
il mio problema non sta nelle definizioni, su quello non ho problemi, ma su come applicarle !! grazie mille per l'aiuto e per iconsigli!! 
!! grazie mille per l'aiuto e per iconsigli!!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo