이 로그 부등식을 어떻게 효율적으로 풀 수 있습니까?

Question

부등식은 다음과 같습니다. nlogn < = a (n은 자연수이며 로그는 10을 기준으로 함). 질문 : 가능한 최대 값은 무엇입니까?

내 해결책은 nlogn> a.가되는 지점에 도달 할 때까지 n = 1에서 무한대까지 (1 단계) 스캔하는 것입니다. 반환 된 결과는 n - 1 일 것입니다.

그러나 매우 커서 a가 매우 효율적이라는 것을 알았습니다. 누구든지 그것을 해결하는 좋은 아이디어가 있습니까?

Answer 1

나는 comingstorm의 해법에 대한 대수를 적절히 수행하여 구현했습니다. 내 컴퓨터에서 Newton의 방법은 4의 인수로 이진 검색보다 높습니다. 모든 음이 아닌 32 비트 정수에 newton()을 테스트했습니다.

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

Answer 2

이진 검색으로 처리하십시오. 시작 간격은 (1, a) 또는 (sqrt (a), a) 일 수 있습니다.

Answer 3

nlogn = a 방정식을 풀면 비교할 때마다 계산을 수행하지 않아도됩니다. 방정식은 Transcendental equation이므로 일정 시간 반복을 사용하면 매우 좋은 근사치를 얻을 수 있습니다. 그런 다음 데이터에 Binary Search을 수행하십시오.

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

Answer 4

이진 검색은 신뢰할만한 답변입니다. 이와 같은 방정식을 풀 수있는 또 다른 방법은 x = f (x)로 다시 쓰고 f (x), f (f (x)), f (f (f))) 등을 다룬다. 결과가 수렴 되길 바랍니다. | f '(x) | < 1. n log n = a를 n = a/log n으로 다시 작성하는 것은 실제로 놀랍도록 잘 작동하는 것처럼 보입니다.