如何以有效的方式解決這種對數不等式？

Question

不等式是：nlogn < = a（n是自然數，log是基於10）。問題：n可能的最大值是多少？

我的解決方案是掃描n = 1到無限（步驟1），直到達到nlogn> a的點。返回的結果是n - 1

但是我發現當a非常大時，這個效率不高。有沒有人有一個好主意如何解決它？

Answer 1

我正確地做了暴風影音解決方案的代數並做了一個實現。在我的機器上，牛頓的方法比二分搜索優勝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（x）））等等，並且希望結果收斂。如果| f'（x）|有這個希望< 1.重寫n log n = a，因爲n = a/log n似乎在實踐中出人意料地運作良好。