Tu pregunta no está muy bien definida.
En primer lugar, puede construir fácilmente un contraejemplo de lo que está preguntando. Suponga que el “número muy grande [matemática] c [/ matemática]” es [matemática] 1000 [/ matemática]. Luego, ajuste [matemática] f (n) = 1001. [/ matemática] Puede ver que independientemente de “cuán grande” sea su [matemática] n [/ matemática], la función [matemática] f [/ matemática] nunca satisfará [matemáticas] (n) <n [/ matemáticas]
Ahora, algunas funciones son especiales, por ejemplo, si una función está aumentando estrictamente , entonces puede aplicar un método similar a la búsqueda binaria en el intervalo [matemáticas] [1, c] [/ matemáticas]. Lo haces de la siguiente manera:
- ¿La falta de competencia matemática interrumpiría mi facilidad de aprendizaje de programación?
- ¿Se puede descifrar algún código?
- ¿Qué procesos se modelan mejor mediante una distribución exponencial? ¿Cómo se relaciona la función exponencial con tales procesos?
- ¿Cuáles son las ventajas del costeo variable?
- ¿Por qué la gente cree que todos los teoremas sobre las máquinas de Turing son válidos cuando se habla de una computadora?
Deje [math] q = \ left \ lceil {\ frac {1 + c} {2}} \ right \ rceil [/ math]
Verifique si [matemáticas] f (q) <c [/ matemáticas] o no. Si [matemática] f (q) <c [/ matemática], entonces verifica el intervalo [q, c] pero si no es así, verifica el intervalo [1, q]. ¡Sigue repitiendo este proceso hasta que su intervalo tenga solo un número, y haya encontrado su n!
Dado que sigue dividiendo el intervalo a la mitad constantemente, esencialmente lo está haciendo en el peor de los casos [math] \ log_2 (c-1) [/ math] operaciones de división. Dentro de cada uno de ellos, solo está verificando una condición que requiere tiempo constante independientemente de cuán grande sea [math] q [/ math]. Por lo tanto, su tiempo de ejecución es [math] O (\ log_2 (c-1)) \ times O (1)) [/ math] o simplemente [math] O (\ log (c)) [/ math]
