麻烦嵌套的循环运行时间 [英] Trouble with nested for-loop running time
问题描述
我一直在思考过这个问题了几天,现在和我挂了计算时代的第二个嵌套的循环运行的次数。我相信,我有正确的公式,用于确定运行时间对于其他两个for循环,但该第三人有我挂断了电话。我的第一个循环运行N-1次。等式确定的倍环路#2是运行的数量; 1至n-1的总和。如果有人可以帮助我了解如何找到时间循环#3的运行数量将大大AP preciated。
的for(int i = 1; I< = N-1;我++){
对于(INT J = I + 1; J< = N; J ++){
对于(INT K = 1; K< = j的; k ++){
}
}
}
第三循环运行C倍:
C = SUM(SUM(SUM(1,K = 1 .. j)中,J = I + 1。N),I = 1 ... N-1)
=萨姆(萨姆(J,J = i + 1的。N)中,i = 1 ... N-1)的
= 2 + 3 + 4 + ... + N
+ 3 + 4 + ... + N
...
+ N
= 2 * 1 + 3 * 2 + 4 * 3 + 5 * 4 + ... + N *(N-1)
=(1 * 1 + 1)+(2 * 2 + 2)+(3 * 3 + 3)+ ... +((N-1)*(N-1)+ N-1)的
=(1 ^ 2 + 2 ^ 2 + ......第(n-1)^ 2)+(1 + 2 + 3 + ... +(N-1))
=(N-1)* N *(2 * N-1)/ 6 +(N-1)* n / 2个
=(N-1)* N *(2 * N + 2)/ 6
=为O(n ^ 3)
在这里,我使用的公式:
1 ^ 2 + 2 ^ 2 + ... + M ^ 2 = M *(M + 1)×(2×M + 1)/ 6
和
1 + 2 + ... + M = M *(M + 1)/ 2
I have been thinking over this problem for a few days now and am hung up on calculating the number of times the second nested for-loop will run. I believe that I have the correct formula for determining the running time for the other two for-loops, but this third one has me hung up. I have the first loop running n-1 times. The equation to determine the number of times loop #2 runs is; The summation of 1 to n-1. If anyone could help me understand how to find the number of times loop #3 runs it would be greatly appreciated.
for ( int i=1; i<=n-1; i++ ) {
for ( int j=i+1; j<=n; j++ ) {
for ( int k=1; k<=j; k++ ) {
}
}
}
The third loop runs C times:
C = Sum( Sum ( Sum ( 1 , k = 1 .. j ) , j = i+1 .. n ) , i = 1 .. n-1 )
= Sum( Sum ( j , j = i+1 .. n ) , i = 1 .. n-1 )
= 2 + 3 + 4 + ... + n
+ 3 + 4 + ... + n
...
+ n
= 2*1 + 3*2 + 4*3 + 5*4 + ... + n*(n-1)
= (1*1 + 1) + (2*2 + 2) + (3*3 + 3) + ... + ((n-1)*(n-1) + n-1)
= (1^2 + 2^2 + ... (n-1)^2) + (1 + 2 + 3 + ... + (n-1))
= (n-1)*n*(2*n-1)/6 + (n-1)*n/2
= (n-1)*n*(2*n+2)/6
= O(n^3)
Here I used the formulas:
1^2 + 2^2 + ... + m^2 = m*(m+1)*(2*m+1)/6
and
1 + 2 + ... + m = m*(m+1)/2
这篇关于麻烦嵌套的循环运行时间的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!