求下列程序段时间复杂度，请写出分析过程
sum=0;for（i=0；i<N;i++）for(j=0;j<i*i;j++)sum++;...
sum = 0;
for（i = 0；i < N; i++）
for (j = 0;j < i * i; j++)
sum++; 展开
for（i = 0；i < N; i++）
for (j = 0;j < i * i; j++)
sum++; 展开
展开全部
外循环执行N次，而每次内循环执行i^2次，所以时间复杂度是：
O(1^2+2^2+...+(N-2)^2+(N-1)^2)
再利用公式：
1^2+2^2+...+(N-1)^2=N*(N-1)*(2*N-1)/6
可得时间复杂度是：O(N^3)
O(1^2+2^2+...+(N-2)^2+(N-1)^2)
再利用公式：
1^2+2^2+...+(N-1)^2=N*(N-1)*(2*N-1)/6
可得时间复杂度是：O(N^3)
已赞过
已踩过<
评论
收起
你对这个回答的评价是？
推荐律师服务：
若未解决您的问题，请您详细描述您的问题，通过百度律临进行免费专业咨询
