/ / w jaki sposób skutecznie rozwiązujesz tę nierówność logarytmiczną? - algorytm, równanie, nierówność

w jaki sposób skutecznie rozwiązujesz tę nierówność logarytmiczną? - algorytm, równanie, nierówność

Nierówność to: nlogn <= a (n to liczba naturalna, log to 10). Pytanie: jaka jest maksymalna wartość n możliwego?

Moim rozwiązaniem jest skanowanie n = 1 do nieskończoności (krok 1), aż do momentu, w którym nlogn> a. Zwrócony wynik byłby n - 1

Ale dowiedziałem się, że nie jest to skuteczne, gdy jest bardzo duże. Czy ktoś ma dobry pomysł, jak go rozwiązać?

Odpowiedzi:

8 dla odpowiedzi № 1

Zrobiłem algebrę dla rozwiązania burzy mózgów prawidłowo i wykonałem implementację Na mojej maszynie metoda Newtona bije wyszukiwanie binarne przez współczynnik 4. Testowałem newton() na wszystkich nieujemnych 32-bitowych liczbach całkowitych.

#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);
}

5 dla odpowiedzi nr 2

Zrób to za pomocą wyszukiwania binarnego. Interwał początkowy może wynosić (1, a) lub (sqrt (a), a).


1 dla odpowiedzi nr 3

Jeśli rozwiążesz równanie nlogn = a, możesz uniknąć wykonywania tych obliczeń za każdym razem, gdy wykonasz porównanie. Równanie to Równanie transcendentalne, więc ciągły czas iteracji może dać ci wynik, który jest dość dobrym przybliżeniem. Następnie wykonaj a Wyszukiwanie binarne na twoich danych.

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

0 dla odpowiedzi nr 4

Wyszukiwanie binarne jest dobrą, niezawodną odpowiedzią. Innym sposobem rozwiązania takich równań jest przepisanie ich jako x = f (x), a następnie wypracowanie f (x), f (f (x)), f (f (f (x))) i tak dalej, i mam nadzieję, że wynik zbiega się. Jest na to nadzieja, jeśli | f "(x) | <1. Przepisanie n log n = a jako n = a / log n wydaje się zadziałać zaskakująco dobrze w praktyce.