一个大O的分析
sum = 0;
for( i = 1; i < n; i++)
for(j = 1; j < i * i; j++)
if( j % i == 0)
for( k = 0; k < j; k++)
sum++
我的分析是 = O(N^3)
但是验证时,好像不对,麻烦高手指点
[解决办法]
sum = 0;
for( i = 1; i < n; i++) --- n
for(j = 1; j < i * i; j++) --- 1+2^2+..+n^2 =n(n+1)(2n+1)/6 =O(n^3)
if( j % i == 0) --- 1 - i^2 中有i个 ,即运行 n(n+1)/2次
for( k = 0; k < j; k++) --- 对 i+2i+...+ii =i(i+1)i/2 求和
sum++
即 对(i^3+i^2)/2求和 ,是O(n^4)的