¿Cómo resuelves esta desigualdad logarítmica de una manera eficiente? - Algoritmo, ecuación, desigualdad

La desigualdad es: nlogn <= a (n es el número natural, el registro se basa en 10). Pregunta: ¿cuál es el valor máximo de n posible?

Mi solución es escanear n = 1 hasta el infinito (paso 1) hasta llegar al punto donde nlogn> a. El resultado devuelto sería n - 1

Pero descubrí que esto no es eficiente cuando a es muy grande. ¿Alguien tiene una buena idea de cómo resolverlo?

Respuestas

Hice el álgebra para la solución de tormentas venideras y realicé una implementación. En mi máquina, el método de Newton mejora la búsqueda binaria por un factor de 4. He probado newton() en todos los enteros de 32 bits no negativos.

#include <assert.h>
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <time.h>

static int newton(double a) {
if (a < 2.0 * log10(2.0)) {
return 1;
} else if (a < 3.0 * log10(3.0)) {
return 2;
}
double a_log_10 = a * log(10);
double x = a / log10(a);
x = (x + a_log_10) / (1.0 + log(x));
x = (x + a_log_10) / (1.0 + log(x));
double n = floor(x);
if (n * log10(n) > a) {
n--;
} else if ((n + 1.0) * log10(n + 1.0) <= a) {
n++;
}
return n;
}

static int binarysearch(double a) {
double l = floor(a / log10(a));
double u = floor(a) + 1.0;
while (1) {
double m = floor((l + u) / 2.0);
if (m == l) break;
if (m * log10(m) > a) {
u = m;
} else {
l = m;
}
}
return l;
}

static void benchmark(const char *name, int (*solve)(double)) {
clock_t start = clock();
for (int a = 1 << 22; a >= 10; a--) {
int n = solve(a);
assert(n * log10(n) <= a);
assert((n + 1) * log10(n + 1) > a);
}
printf("%s: %.2fn", name, (clock() - start) / (double)CLOCKS_PER_SEC);
}

int main(int argc, char *argv[]) {
benchmark("newton", newton);
benchmark("binarysearch", binarysearch);
}

Hazlo con una búsqueda binaria. El intervalo de inicio puede ser (1, a) o (sqrt (a), a).

Si resuelve la ecuación nlogn = a, puede evitar realizar ese cálculo cada vez que haga una comparación. La ecuación es una Ecuación trascendental, entonces una iteración de tiempo constante podría obtener un resultado que es una aproximación bastante buena. Luego realiza un Búsqueda binaria en tus datos.

procedure solve_transcendental
n = 50
for i = 1 .. 20
n = a / log(n)
end
end

La búsqueda binaria es una buena respuesta confiable. Otra forma de resolver ecuaciones como esta es reescribirlas como x = f (x) y luego calcular f (x), f (f (x)), f (f (f (x))) y así sucesivamente, y Espero que el resultado converja. Hay esperanza para esto si | f "(x) | <1. Reescribiendo n log n = a como n = a / log n parece funcionar sorprendentemente bien en la práctica.