Calcolare n in una disequazione
Buonasera a tutti, scusate se la risposta alla domanda che vi sto per fare è banale, ma io non riesco a trovarla:
Su due macchine identiche vengono implementati due algoritmi differenti, uno impiega $8*n^2 $ passi, mentre l'altro impiega $64*n*log(n) $ passi. Per quali valori di n, il primo algoritmo batte il secondo? Con $ log(n) $ si intende logaritmo in base 2 di n.
Ho provato a svolgerlo:
Ho scritto la disequazione $ 8*n^2 < 64*n*log(n) $
Arrivo alla conclusione che $ 8*log(n) < n $
Come continuo?
Grazie in anticipo, come sempre
Su due macchine identiche vengono implementati due algoritmi differenti, uno impiega $8*n^2 $ passi, mentre l'altro impiega $64*n*log(n) $ passi. Per quali valori di n, il primo algoritmo batte il secondo? Con $ log(n) $ si intende logaritmo in base 2 di n.
Ho provato a svolgerlo:
Ho scritto la disequazione $ 8*n^2 < 64*n*log(n) $
Arrivo alla conclusione che $ 8*log(n) < n $
Come continuo?
Grazie in anticipo, come sempre
Risposte
Io direi $n<8*log(n)$ ... comunque non è risolvibile analiticamente ma usando qualche metodo numerico (anche solo bisezione)
Grazie per la risposta
Si scusa ho sbagliato, volevo scrivere $ n < 8 log (n) $
Quindi per via numerica come posso risolverlo? Assegnando valori arbitrari a n, oppure c'è un altro modo?
PS. Ho trovato l'esercizio svolto su un sito che riporta questa soluzione qui (ma per me non ha senso provare per n=2 perché il problema chiede nello specifico tutti gli n tali che quella disequazione sia soddisfatta). Forse sono soluzioni taroccate?
https://www.chegg.com/homework-help/introduction-to-algorithms-3rd-edition-chapter-1.2-problem-2e-solution-9780262033848
Si scusa ho sbagliato, volevo scrivere $ n < 8 log (n) $
Quindi per via numerica come posso risolverlo? Assegnando valori arbitrari a n, oppure c'è un altro modo?
PS. Ho trovato l'esercizio svolto su un sito che riporta questa soluzione qui (ma per me non ha senso provare per n=2 perché il problema chiede nello specifico tutti gli n tali che quella disequazione sia soddisfatta). Forse sono soluzioni taroccate?
https://www.chegg.com/homework-help/introduction-to-algorithms-3rd-edition-chapter-1.2-problem-2e-solution-9780262033848
La disequazione $ n < 8 log_2 n $ è verificata per tutti i valori di $ n \in NN $ (dato che si tratta di passi) tali che $ 2 \le n \le 43 $ (42 soluzioni). Io la risolverei graficamente, osservando dove la retta $ y = frac{n}{8} $ sta sotto la funzione $ y = log_2 n$.
Grazie @pilloeffe 
E come faccio quindi a risolverlo in questo modo? Come faccio a vedere quali sono i valori per i quali la prima funzione si trova sotto la seconda?
E come faccio quindi a risolverlo in questo modo? Come faccio a vedere quali sono i valori per i quali la prima funzione si trova sotto la seconda?
pilloeffe ti dice semplicemente di disegnare il grafico delle due funzioni (con un sw ovviamente) e vedere "visivamente" quando una funzione si trova sotto l'altra ... dato che ti servono solo numeri interi, dovrebbe essere sufficiente ... altrimenti cerca in rete il metodo di bisezione o quello di Newton per risolvere equazioni (sicuramente meglio di come li potrei spiegare io qui ...)
Ciao Programmer,
Come ti ha detto giustamente @axpgn, per vedere dove si intersecano quelle due funzioni occorrono metodi numerici. Poiché però sappiamo che $n$ deve essere un numero naturale, le cose si semplificano e basta disegnare un grafico qualitativo (eventualmente anche "a mano", con una semplice tabella $x|y$...) delle due funzioni. Si vede subito che $ n = 1$ non va bene; da $n = 2$ in poi invece la disequazione è verificata e continua ad esserlo fino a $n = 32$ (sto facendo uso delle potenze di 2 per comodità). $n = 64$ invece non va bene, quindi il secondo numero naturale cercato è maggiore di 32 e minore di 64. Andando avanti di 10 da 32 si trova che $n = 42$ va ancora bene, così come il successivo $n = 43$. Per $n = 44$ invece la disequazione non è più verificata, quindi il secondo numero naturale cercato è $n = 43$.
Per tua maggiore comodità, ecco qui di seguito il grafico delle due funzioni $ y = frac{x}{8}$ e $ y = log_2 x$ fatto col software WolframAlpha:
https://www.wolframalpha.com/input/?i=x%2F8+%3C+log_2+x
Come ti ha detto giustamente @axpgn, per vedere dove si intersecano quelle due funzioni occorrono metodi numerici. Poiché però sappiamo che $n$ deve essere un numero naturale, le cose si semplificano e basta disegnare un grafico qualitativo (eventualmente anche "a mano", con una semplice tabella $x|y$...) delle due funzioni. Si vede subito che $ n = 1$ non va bene; da $n = 2$ in poi invece la disequazione è verificata e continua ad esserlo fino a $n = 32$ (sto facendo uso delle potenze di 2 per comodità). $n = 64$ invece non va bene, quindi il secondo numero naturale cercato è maggiore di 32 e minore di 64. Andando avanti di 10 da 32 si trova che $n = 42$ va ancora bene, così come il successivo $n = 43$. Per $n = 44$ invece la disequazione non è più verificata, quindi il secondo numero naturale cercato è $n = 43$.
Per tua maggiore comodità, ecco qui di seguito il grafico delle due funzioni $ y = frac{x}{8}$ e $ y = log_2 x$ fatto col software WolframAlpha:
https://www.wolframalpha.com/input/?i=x%2F8+%3C+log_2+x
Scusate se rispondo solo ora, ma non ho avuto tempo per analizzare le soluzioni che mi avete proposto. Ho capito come fare. Vi ringrazio moltissimo
A presto
A presto
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo