这个生成算法的时间复杂度是多少？

哈西B我

我有一个数字生成算法，我想知道它的时间复杂度是多少？

它生成长度为 n 的所有组合。

下面是代码片段

void generate_N_Numbers(int n){
    int len = 0;
    int alphaLen = 2;
    int  *letters  = malloc(n * sizeof(int));

    uint64_t outerLoopCounter = 0,innerLoopCounter1 = 0,innerLoopCounter2 = 0,
    innerLoopCounter3 = 0,innerLoopCounter4 = 0,totalLoopCounter = 0;   


    for (len=1; len<=n; len++)
    {
        outerLoopCounter++;
        int i;
        int stride = len+1;
        int bufLen = stride * alphaLen * alphaLen;

            if (len == 1) 
            continue;

        for (i=len-2; i<bufLen; i+=stride)
            innerLoopCounter1++;


        if (len == 2)
            continue;

        for (i = 0; i < len;i++){
        letters[i] = 0; 
        innerLoopCounter2++;
        }

    i = len-3;
    do {
        int  j;
        innerLoopCounter3++;

        letters[i]++;


        if (letters[i] >= alphaLen)
        letters[i] = 0;

        for (j=i;j<bufLen;j+=stride){
        innerLoopCounter4++;
        }

        if (letters[i] != 0) {
        i = len - 3;
        continue;
        }

        i--;

        if (i < 0)
        break;

    } while(1);

    }

}

这是此代码的链接。https://ideone.com/HxzDGv

这是输入 1 到 30 的算法结果的链接。https://pastebin.com/LwavAff1

我猜它的复杂度是O(n2)但我仍然不确定这一点。并且这个循环比以某种方式具有 O(n) 时间复杂度的循环更快地生成数字。

蒂姆D1

是的，您假设运行时间为 O(n^2) 是正确的。要考虑的代码中最昂贵的部分是两个循环内的部分；所有其他部分都无关紧要，并且需要 O(1) 时间。

您的外for循环将运行 n 次，每个内for循环将运行 O(n) 次。

您的do-while循环将执行少于 n 次，并且其中的for循环最多执行 n 次。

请注意，最内层for循环中的所有操作都是 O(1)。

总结这些信息，需要 n*(n*1+n*1) + n*n*1 个操作，也就是 O(n^2)

注意：您的代码非常混乱，我没有尝试遵循您所做的事情背后的逻辑；我只是想演示基本的复杂性分析。我建议看一下std::next_permutation。

本文收集自互联网，转载请注明来源。

如有侵权，请联系 [email protected] 删除。