寻找这两种算法的时间复杂度？

Question

这是第一个算法，

sum = 0;
for( i=1; i<n; i++ )
        for( j=0; j<i*n; j++ )
            for( k=0; k<j; k++)
            sum++;

这是第二种算法

sum = 0;
for( i=1; i<n; i++ )
    ( j=1; j<i*n; j++ )
        if( j%1 == 0 )
            for( k=0; k<j; k++ )
                sum++;

谁能帮我找到这两个算法的大O？我尝试这样做并且得到了 n^5 但是当我通过比较 n^5 和这些算法的算法的运行次来检查它时，存在巨大差异...... 虽然这两种算法的运行次差不多，这意味着它们的时间复杂度是一样的。

如果有人可以，请提供一种可能的方法来分析这两种算法并找出两者的时间复杂度。谢谢

注意：我也尝试将它与 n^4 次的算法进行比较，运行次之间仍然存在巨大差异......我也可以提供 [=22= 的值] 所有这些不同算法的时间（如果需要）。

Answer 1

第一个算法的时间复杂度如下：

sum_{i=1}^{n-1} sum_{j=1}^{i*n} j =
sum_{i=1}^{n-1} i * n * (i*n + 1) / 2 = 
0.5 * sum_{i=1}^{n-1} i^2 * n^2 + i*n = 
0.5 * (n^2 * sum_{i=1}^{n-1} i^2 + n * sum_{i=1}^{n-1} i) = 
0.5 * (n^2 * \Theta(n^3) + n * \Theta(n^2)) = \Theta(n^5)

所以，你是对的。但请注意，这是渐近时间复杂度，可能与测量的 CPU 运行时间不同。

第二个算法也是一样的（有细微差别），一如既往，j%1对所有j > 0都等于0。

寻找这两种算法的时间复杂度？

Finding Time Complexity of these two algorithms?

algorithm

time

complexity-theory

big-o

time-complexity