ALGORITMOS E IMPLEMENTAÇÕES ⇒ Análise de algoritmos

[vini_scien]

Supunha que você cronometrou um programa como função de N e produziu a seguinte tabela.

Código: Selecionar todos

      N       seconds
-------------------
      128     0.000
      256     0.001
      512     0.003
     1024     0.017
     2048     0.084
     4096     0.444
     8192     2.335
    16384    12.314
    32768    64.367
    65536   337.235
   131072  1752.094

Estime a ordem de crescimento do tempo de execução como função de N. Suponha que o tempo de execução obedece a lei da potência [tex3]T(N) \approx a * N^b[/tex3]. Para sua resposta, dê a constante b. Sua resposta estará correta se estiver dentro de 1% da resposta alvo. É recomendado que você use dois dígitos de precisão. Ex: 1.34

[tex3]b = 2.38[/tex3]