Anonimo
Anonimo ha chiesto in Matematica e scienzeMatematica · 4 sett fa

Problema di matematica?

Supponiamo di avere una funzione f così definita:

f = c*x^2

e una funzione g così definita:

g = k * lg_2(x)

(c) e (k) sono costanti. Se non ci fossero è chiaro che g cresce più lentamente di f. Ora, sia k>c al punto che localmente g cresce più velocemente di f, ma a un certo punto la crescita esponenziale prenderà il sopravvento. Come si calcola il punto in cui le due funzioni "si toccano"?

Aggiornamento:

In particolare ho il seguente problema: l'algoritmo A impiega 8*n^2 passi per essere eseguito, mentre B impiega 64n * log_2(n) passi. Per quali valori di n l'algoritmo B batte (cioè impiega meno tempo) di A?

2 risposte

Classificazione
  • Anonimo
    4 sett fa
    Risposta preferita

    Devi risolvere

    8 n^2 >= 64 n log_2(n)

    ovvero devi studiare per quali  valori positivi di x

    y = 64 x log_2(x) - 8x^2 é definitivamente negativa

    tracciamo il grafico per avere un'idea

    https://www.desmos.com/calculator/qition6nc3

    per via euristica  ( tentativi, bisezione, tangenti )  n = 44.

  • DIEGO.
    Lv 6
    4 sett fa

                                   

Altre domande? Fai una domanda e ottieni le risposte che cerchi.