具有 1 个循环的函数的复杂性

Question

谁能告诉我下面这个函数的复杂度是多少？以及如何计算复杂度？

我怀疑它是 O(log(n)) 或 O(sqrt(N))。我的推理基于以 n=4、n=8、n=16 为例，我发现循环将采用 log(n) 但我认为这还不够，因为 sqrt 也会给出相同的值所以我需要研究更大的 n 值，所以我不确定如何处理这个问题。

今天考试有这个功能

void f(int n){
     int i=1;
     int j=1;
     while(j <= n){
         i += 1;
         j += i;
     }
}

Answer 1

序列 j 经过的是 1 3 6 10 15 21，又名三角数，又名 n*(n+1)/2。

展开，这是( n^2 + n ) / 2。我们可以忽略缩放 ( / 2) 和线性 ( + n) 因素，这给我们留下了 n^2.

j 增长为 n^2 多项式，因此循环将在该增长的倒数后停止：

时间复杂度为O(sqrt(n))

Answer 2

这取决于你的情况。换句话说，时间复杂度是 O(log n)。相对于输入大小 n，执行了多少条语句？经常，但并非总是如此，我们可以从循环次数中得到一个想法迭代。循环体执行 for i= 2^0 + 2^1 + 2^2 + .... + 2^n;还有这个序列有 O(log n) 个值。

查看 "Introduction to Algorithms" 书中的更多详细信息。

Answer 3

为了它的价值，我编写了一个小程序，试图通过实际计算循环执行的迭代次数来说明这是 O(log(N)) 还是 O(sqrt(N))。这似乎是一个合理的近似值，因为循环体在很大程度上可以忽略不计（只需递增两个整数变量）。

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

int f(int n)
{
    int i=1;
    int j=1;
    int count = 0;

    while(j <= n){
        i += 1;
        j += i;
        count++;
    }

    return count;
}

int main()
{
    for (int ii = 0; ii < 10; ii++) {
        int count = pow(10, ii);
        int rc = f(count);
        char *fmt = "N=%d^%-2d -> %d, log(N)=%.2f, sqrt(N)=%.2f\n";
        printf(fmt, 10, ii, rc, log(count), sqrt(count));
    }

    return 0;
}

运行此代码产生以下输出：

N=10^0  -> 1, log(N)=0.00, sqrt(N)=1.00
N=10^1  -> 4, log(N)=2.30, sqrt(N)=3.16
N=10^2  -> 13, log(N)=4.61, sqrt(N)=10.00
N=10^3  -> 44, log(N)=6.91, sqrt(N)=31.62
N=10^4  -> 140, log(N)=9.21, sqrt(N)=100.00
N=10^5  -> 446, log(N)=11.51, sqrt(N)=316.23
N=10^6  -> 1413, log(N)=13.82, sqrt(N)=1000.00
N=10^7  -> 4471, log(N)=16.12, sqrt(N)=3162.28
N=10^8  -> 14141, log(N)=18.42, sqrt(N)=10000.00
N=10^9  -> 44720, log(N)=20.72, sqrt(N)=31622.78

所以，比如你可以看到，当N=10^9时，迭代次数为44720，比log(N)(20.72)大很多，但很接近sqrt(N)(31622.78) ).

具有 1 个循环的函数的复杂性

Complexity of a function with 1 loop

c++

algorithm

big-o

time-complexity