指定线路运行次数的边界函数（Big-O）是多少？（C）

我想抓住运行时的概念，并且我对这个问题有点困惑。我知道外部循环的运行时间是O（n）。我也知道n的值大于1000，内部循环将运行在恒定的时间。但是，对于n < 1000的值，内部循环似乎具有对数运行时。那么这是否意味着该函数的大O将会是O（n log n），因为我应该假设最坏的情况？指定线路运行次数的边界函数（Big-O）是多少？（C）

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

来源

2017-07-25 SirOxorsid

大O符号描述了当n接近无穷大时的行为。 A = O（B）其中A和B是n的函数，意味着当n接近正无穷大时A/B的极限小于正无穷大。
因此，n = 1000以下的情况不会影响大O符号。

来源

2017-07-25 23:46:43

该代码的渐近运行时是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上界。

来源

2017-07-26 00:22:46

请注意，对于任何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）。

来源

2017-07-26 00:26:32 templatetypedef

指定线路运行次数的边界函数（Big-O）是多少？ （C）

回答

相关问题

指定线路运行次数的边界函数（Big-O）是多少？（C）