Как вы решаете это логарифмическое неравенство эффективным способом? - PullRequest
Новая
       29

Как вы решаете это логарифмическое неравенство эффективным способом?

1 голос
/ 17 сентября 2011

Неравенство: nlogn <= a (n - натуральное число, log основано на 10). Вопрос: какое максимальное значение n возможно? </p>

Мое решение состоит в том, чтобы сканировать n = 1 до бесконечности (шаг 1) до достижения точки, где nlogn> a. Возвращенный результат будет n - 1

Но я обнаружил, что это неэффективно, когда а очень велико. У кого-нибудь есть хорошая идея, как ее решить?

Ответы [ 4 ]

7 голосов
/ 17 сентября 2011

Я правильно выполнил алгебру для решения comestorm и сделал реализацию. На моей машине метод Ньютона превосходит двоичный поиск в 4 раза. Я протестировал newton() на всех неотрицательных 32-битных целых числах. 

#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: %.2f\n", name, (clock() - start) / (double)CLOCKS_PER_SEC);
}

int main(int argc, char *argv[]) {
    benchmark("newton", newton);
    benchmark("binarysearch", binarysearch);
}
5 голосов
/ 17 сентября 2011

Сделайте это с помощью бинарного поиска. Начальный интервал может быть (1, a) или (sqrt (a), a).

1 голос
/ 17 сентября 2011

Если вы решите уравнение nlogn = a, вы можете избежать выполнения этого вычисления при каждом сравнении. Уравнение представляет собой трансцендентное уравнение , поэтому итерация с постоянным временем может дать вам довольно хороший результат. Затем выполните двоичный поиск по вашим данным. 

procedure solve_transcendental
   n = 50
   for i = 1 .. 20
      n = a / log(n)
   end
end
0 голосов
/ 17 сентября 2011

Двоичный поиск - хороший надежный ответ. Другой способ решения таких уравнений - переписать их как x = f (x), а затем вычислить f (x), f (f (x)), f (f (f (x))) и т. Д., И надеюсь, что результат сходится. На это есть надежда, если | f '(x) | <1. Переписывание n log n = a как n = a / log n на практике работает на удивление хорошо. </p>

...