指定線路運行次數的邊界函數（Big-O）是多少？ （C）

Question

我想抓住運行時的概念，並且我對這個問題有點困惑。我知道外部循環的運行時間是O（n）。我也知道n的值大於1000，內部循環將運行在恆定的時間。但是，對於n < 1000的值，內部循環似乎具有對數運行時。那麼這是否意味着該函數的大O將會是O（n log n），因爲我應該假設最壞的情況？

for(i = 1; i < n; i++) { 
    for(j = 1000/i; j > 0; j--) { 
    arr[j]++;  <-------- THIS LINE 
    } 
} 

Answer 1

大O符號描述了當n接近無窮大時的行爲。 A = O（B）其中A和B是n的函數，意味着當n接近正無窮大時A/B的極限小於正無窮大。
因此，n = 1000以下的情況不會影響大O符號。

Answer 2

該代碼的漸近運行時是O（1）即不管n多大，存在一個常數即<=比執行線arr[j]++;的次數，而且恆定恰好是相當小。

證明：

#include <stdio.h> 

long long int test(long long int n) { 
    long long int ct = 0; 
    long long int i, j; 
    for (i = 1; i < n; i++) { 
     for (j = 1000/i; j > 0; j--) { 
      ct ++; 
     } 
    } 
    return ct; 
} 

int main(void) { 
    long long int n; 
    for (n = 1; n < 100000000; n *= 10) { 
     printf("testing with n = %lld: ct = %lld\n", n, test(n)); 
    } 
} 

輸出是

testing with n = 1: ct = 0 
testing with n = 10: ct = 2827 
testing with n = 100: ct = 5132 
testing with n = 1000: ct = 7068 
testing with n = 10000: ct = 7069 
testing with n = 100000: ct = 7069 
testing with n = 1000000: ct = 7069 
testing with n = 10000000: ct = 7069 

它是由硬常數7069，這是從未超過，因爲當n超過1000時，該商將爲0上界。

Answer 3

請注意，對於任何n> 1000，內部循環根本不會運行 - 當將因子分解爲整數時，j的起始值爲零。因此，在n超過1000之後，內部循環運行的次數完全獨立於n - 只有外部循環的前1000次迭代纔會執行內部語句。

由於從長期來看，內部循環的迭代次數與n無關，在大O的意義上，所指示的語句運行O（1）次。

但是，如果您保持較小的值，您會看到循環運行次數的對數增長。請注意，當i = 1時，循環運行1000次，當i = 2時運行1000/2次，等等。忽略向下舍入的效果，經過k次外循環迭代後，內循環將運行

1000 + 1000/2 +三分之一千+ ... + 1000/K

= 1000（1/1 + 1/2 1/3 + + ... + 1/K）

= 1000H _ķ

倍，其中H _ķ是第k harmonic number。第k次諧波數爲Θ（log k），因此忽略循環迭代次數舍入的影響將以對數形式增長。總之，在短期內增長是對數的，但由於整數除法的答案是O（1）。