как эффективно решить это логарифмическое неравенство?

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

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

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


algorithm equation inequality
person Community    schedule 17.09.2011    source источник

Ответы (4)


arrow_upward
7
arrow_downward

Я правильно сделал алгебру для решения грядущей бури и сделал реализацию. На моей машине метод Ньютона превосходит двоичный поиск в 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);
}
person the guy formerly known as d    schedule 17.09.2011
comment
Вы также можете выполнить итерацию Netwon по исходной проблеме. d(n log n)/dn = (log n + log e), поэтому шаг должен быть n += (a-n*log(n))/(log n + log e) - person comingstorm; 17.09.2011

arrow_upward
5
arrow_downward

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

person Karoly Horvath    schedule 17.09.2011

arrow_upward
1
arrow_downward

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

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

arrow_upward
0
arrow_downward

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

person mcdowella    schedule 17.09.2011