Quel est le plus grand n pour lequel on peut résoudre en une seconde?

Question

Ceci est un exercice suggéré dans le livre Rosen Discrete Mathematics. Je ne cherche pas la réponse, j'ai déjà la réponse. Je cherche quelqu'un pour aider à expliquer les étapes/moyens/procédures (qu'avez-vous) il faut pour obtenir la réponse.

La question est:

Quel est le plus grand n pour lequel on peut résoudre en une seconde un problème en utilisant un algorithme qui nécessite f (n) opérations de bits, où est effectué chaque opération de bits en 10^- 9 secondes, avec ces fonctions f (n)? Partie C:

c. n * log (n) Je sais que la réponse est:

f (n) = < 10^9

n * log (n) = < 10^9

n < = 3.96x10^7 donc n doit être 3.96x10^7

Le manuel de solution a donné cette réponse, mais il ne me dit pas comment obtenir la réponse. Que dois-je faire pour obtenir

n < = 3.96x10^7 de:

n * log (n) < = 10^9

Merci beaucoup à tous ceux qui me aide à comprendre ce

Answer 1

Je vais essayer, mais peut-être que je me trompe. Ainsi, à partir

n * log (n) = < 10^9

vous obtenez: n^n < 10^(10^9) (J'espère que je ne me trompe pas). Et ici je pense que vous devez essayer de trouver un nombre qui s'élève à lui-même donne moins de 10^(10^9). Et en essayant, ils trouvent 3.96x10^9

Answer 2

Cela s'appelle "mathématiques numériques". La plupart des problèmes du monde réel ne peuvent pas être résolus par un réarrangement de termes dans une formule, mais doivent être approximés. Dans ce cas: Vous voulez résoudre

n ln (n) = 10^9 or n = 10^9/ln (n). 

faire une estimation très approximative n = 10^9. Substituer n dans la deuxième formule: n = 10^9/ln (n), donne n = 4,8255 x 10^7.

Substitut n fois: n = 4,8255 x 10^7/ln (4,8255 x 10^7), on obtient n = 5,6253 x 10^7.

Substitut n fois: n = 5,6253 x 10^7/ln (5,6253 x 10^7), on obtient n = 5,6022 x 10^7.

Substitut n fois: n = 5,6022 x 10^7/ln (5,6022 x 10^7), on obtient n = 5,6050 x 10^7.

Substitut n fois: n = 5,6050 x 10^7/ln (5,6050 x 10^7), on obtient n = 5,6048 x 10^7. Le remplacement de n: n = 5,6048 x 10^7/ln (5,6048 x 10^7) donne n = 5,6048 x 10^7.

Impossible de voir d'où proviendrait 3,96 x 10^7.