尋找一個數字的商

Question

有一個給定數字N，我必須找出其中N爲repetitive division給整數的商數。

對於防爆：

N=8 
Numbers Are 2 as: 8/2=4/2=2/2=1 
      5 as 8/5=1 
      6 as 8/6=1 
      7 and 8 

我Aprroach： 所有的N/2+1到N號碼給了我商1所以

Ans: N/2 + Check Numbers from (2, sqrt(N)) 

時間複雜度O(sqrt(N))

有沒有更好的如何做t他的，因爲號碼可以高達10^12，並且可以有很多查詢？

難道是O(1)或O(40)（因爲2^40超過10^12）

Answer 1

讓我們來看看，因爲數量可高達10^12，你可以做的是創建數字2 to 10^6，您可以創建和40陣列，因此每個長度檢查數字是否可以表示爲i^(len-1)+ y，其中i介於2至10^6之間，len介於1至40之間。

所以時間複雜度O(40*Query)

Answer 2

首先，你的算法是不O(sqrt(N))，因爲你忽略你由各檢查數劃分的次數。如果被檢查的號碼是k，則獲得結果之前的分割數（通過上述方法）是O(log(k))。因此複雜性變爲N/2 + (log(2) + log(3) + ... + log(sqrt(N)) = O(log(N) * sqrt(N))。

現在我們已經明白了，算法可能會得到改進。觀察到，通過重複劃分，只有當k^t <= N < 2 * k^t其中t=floor(log_k(N))時，您纔會得到1的檢查號碼k。

也就是k^t <= N < 2 * k^(t+1)。請注意右側嚴格的<。

現在，要弄清楚t，可以使用牛頓 - 拉夫遜方法或泰勒級數來快速獲得對數，並提到複雜性度量here。我們稱之爲C(N)。所以複雜度將是C(2) + C(3) + .... + C(sqrt(N))。如果你可以忽略計算log的成本，你可以得到這個到O(sqrt(N))。

例如，在對於N以上的情況下= 8：

• 2^3 <= 8 < 2 * 2^3：1
• floor(log_3(8)) = 1和8不滿足3^1 <= 8 < 2 * 3^1：0
• floor(log_4(8)) = 1和8不滿足4^1 <= 8 < 2 * 4^1：0
• 4額外從號碼進來5,6,7和8爲8t=1這些數字。

請注意，我們並不需要檢查3和4，但我已這樣做來說明這一點。您可以驗證[N/2..N]中的每個數字都滿足上述不等式，因此需要添加。

如果使用這種方法，我們可以消除重複的分割，並且如果計算對數的複雜度可以忽略不計，則可以將複雜度降至O(sqrt(N))。

Answer 3

如果你想每個查詢查詢O(1)，小於或等於10^12的自然數的哈希表是其他自然數的冪不會大於2,000,000個元素;通過在1到1,000,000的基數上迭代來創建它，遞增所看到的鍵的值;根1,000,000...10,001只需要平方;根10,000...1,001只需要立方體;在此之後，如上所述，最小的根部最多可以進行40次操作。

表中的每個值將表示基本/電源配置的數量（例如，512 -> 2，對應於2^9和8^3）。

Answer 4

測試工具用於驗證功能並評估複雜性的順序。

根據需要編輯 - 其維基

#include <math.h> 
#include <stdio.h> 

unsigned long long nn = 0; 

unsigned repeat_div(unsigned n, unsigned d) { 
    for (;;) { 
    nn++; 
    unsigned q = n/d; 
    if (q <= 1) return q; 
    n = q; 
    } 
    return 0; 
} 

unsigned num_repeat_div2(unsigned n) { 
    unsigned count = 0; 
    for (unsigned d = 2; d <= n; d++) { 
    count += repeat_div(n, d); 
    } 
    return count; 
} 

unsigned num_repeat_div2_NM(unsigned n) { 
    unsigned count = 0; 
    if (n > 1) { 
    count += (n + 1)/2; 
    unsigned hi = (unsigned) sqrt(n); 
    for (unsigned d = 2; d <= hi; d++) { 
     count += repeat_div(n, d); 
    } 
    } 
    return count; 
} 

unsigned num_repeat_div2_test(unsigned n) { 
    // number of integers that repetitive division with n gives quotient one. 
    unsigned count = 0; 

    // increment nn per code' tightest loop 
    ... 

    return count; 
} 

/// 

unsigned (*method_rd[])(unsigned) = { num_repeat_div2, num_repeat_div2_NM, 
    num_repeat_div2_test}; 
#define RD_N (sizeof method_rd/sizeof method_rd[0]) 

unsigned test_rd(unsigned n, unsigned long long *iteration) { 
    unsigned count = 0; 
    for (unsigned i = 0; i < RD_N; i++) { 
    nn = 0; 
    unsigned this_count = method_rd[i](n); 
    iteration[i] += nn; 
    if (i > 0 && this_count != count) { 
     printf("Oops %u %u %u\n", i, count, this_count); 
     exit(-1); 
    } 
    count = this_count; 
    // printf("rd[%u](%u)  = %u. Iterations:%llu\n", i, n, cnt, nn); 
    } 

    return count; 
} 

void tests_rd(unsigned lo, unsigned hi) { 
    unsigned long long total_iterations[RD_N] = {0}; 
    unsigned long long total_count = 0; 
    for (unsigned n = lo; n <= hi; n++) { 
    total_count += test_rd(n, total_iterations); 
    } 
    for (unsigned i = 0; i < RD_N; i++) { 
    printf("Sum rd(%u,%u) --> %llu. total Iterations %llu\n", lo, hi, 
     total_count, total_iterations[i]); 
    } 
} 

int main(void) { 
    tests_rd(2, 10 * 1000); 
    return 0; 
}