#include <stdio.h> int main() { int N = 8; /* for example */ int sum = 0; for (int i = 1; i <= N; i++) for (int j = 1; j <= i*i; j++) sum++; printf("Sum = %d\n",sum); return 0; }
对于每个n值(i变量),j值将为n ^ 2.所以复杂性将是n. n ^ 2 = n ^ 3.那是对的吗？
如果问题变成：
#include <stdio.h> int main() { int N = 8; /* for example */ int sum = 0; for (int i = 1; i <= N; i++) for (int j = 1; j <= i*i; j++) for (int k = 1; k <= j*j; k++) sum++; printf("Sum = %d\n",sum); return 0; }
然后你使用现有的n ^ 3. n ^ 2 = n ^ 5？那是对的吗？
解决方法
我们有i和j< i * i和k < j * j,它是我的数量,x ^ 1 * x ^ 2 *(x ^ 2)^ 2 = x ^ 3 * x ^ 4 = x ^ 7. 特别地,由于1 < i< N我们有O(N)为i循环.由于1<对于第二个循环,我们具有O(n ^ 2),j = i ^ 2 = N ^ 2.扩展逻辑,我们有1<对于第三循环,k≤j^ 2 =(i ^ 2)^ 2 = N ^ 4. 内环到外环,对于每个j循环,我们执行N ^ 4次,对于每个i循环执行N ^ 2次,并且在i循环上最多N次,使总数为N ^ 4 * N ^ 2 * N = N ^ 7 = O(N ^ 7).
