代码之家 › 专栏 › 技术社区 › TreasureGhost

以下函数的时间复杂度是多少

time-complexity

TreasureGhost · 技术社区 · 2 年前

计算的时间复杂性:

void func(int n)
{
    int sum=0;
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=i*i;j+=i)
        {
            sum+=i;
        }
    }
}

我认为时间复杂度是O(n^2),因为外循环运行n次,而内循环对于I的每个值大约运行I次,这意味着内循环将运行1+2+3++n次,即O(n^2),然而,Google Bard表示复杂性为O(n^3),因为嵌套对时间复杂性有乘法效应,这意味着实际迭代量为

n*(1+2+3+…+n)是O(n^3)

但这怎么可能呢?

2 回复 | 直到 2 年前

Guru Stron 2 年前

你的计算是正确的——确实如此 O(n^2) 。内环有步骤 i 所以它将运行~ i*i/i 迭代给出 O(n) 也用于内环。

jhoney12 2 年前

该函数包含两个嵌套循环。外循环运行“n”次,对于外循环的每次迭代,内循环运行的次数等于当前值“i”的平方。

前'n'个自然数之和为 1. + 2. + 3. + + 1+2+3++n,已知为 ( + 1. ) 2. 2. n(n+1) 。对于外循环中的每个“i”,内循环运行 2. 我 2. 时间。

因此,迭代的总次数与 ( + 1. ) 2. n 2. n(n+1) ,导致时间复杂性为 ( 2. ) O(n 2. ).

与Google Bard关于O(n^3)的建议相反,该分析揭示了由于嵌套循环而非三次循环导致的二次时间复杂性。因此,正确的时间复杂度是 ( 2. ) O(n 2. ).

推荐文章

Matthew · 发现程序的时间复杂性

2 年前

TreasureGhost · 以下函数的时间复杂度是多少

2 年前

Abdullah Kassar · std::upper_bound()是线性的吗?c++

2 年前

user129393192 · 这个问题的最优算法是什么?

2 年前

3366784 · 使用序列初始化字符串的时间复杂度是多少?

2 年前

nehacharya · 这个代码的时间复杂度是O(n^2)还是O(nlogn)?

2 年前

control plane · ruby中链表上size调用的时间复杂性

2 年前

learner · 查找最长的子字符串

2 年前

hackrack · 在javascript中,如何返回时间复杂度为O(n)的相同字母元素?

8 年前

data-oil · 在字符串列表中搜索的高效快捷方法

8 年前