як ви ефективно вирішуєте цю логарифмічну нерівність? - алгоритм, рівняння, нерівність

Нерівність: nlogn <= a (n - це натуральне число, log заснований на 10). Питання: яка максимальна величина n можлива?

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

Але я дізнався, що це неефективно, коли дуже велике. Хто-небудь має хорошу ідею, як її вирішити?

Відповіді:

Я виконував алгебру для прийняття рішення про шорт і правильно виконав його. На моїй машині метод Ньютона б'ється в бінарному пошуку в 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: %.2fn", name, (clock() - start) / (double)CLOCKS_PER_SEC);
}

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

Зробіть це за допомогою бінарного пошуку. Інтервал запуску може бути (1, а) або (sqrt (a), a).

Якщо ви вирішите рівняння nlogn = a, ви можете уникнути виконання цього підрахунку кожного разу, коли ви робите порівняння. Рівняння є a Трансцендентне рівняння, так що постійна ітерація часу може отримати вам результат, який є досить гарним наближенням. Потім виконайте a Бінарний пошук на ваших даних.

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

Двійковий пошук є надійною і надійною відповіддю. Інший спосіб вирішити такі рівняння полягає в тому, щоб переписати їх як x = f (x), а потім розробити f (x), f (f (x)), f (f (f (x))) і так далі, і сподіваюся, що результат сходиться. Існує надія на це, якщо | f "(x) | <1. Переписати n log n = a, як n = a / log n, на практиці на подив добре.