什么是总频率计数和运行时间（Big-O 表示法）？

发布于 2024-08-22 06:34:03 字数 520 浏览 3 评论 0原文

我有以下代码片段：

1. for (i = 1; i < n; i++) 
2.    for (j = 1; j < i*i; j++) 
3.      if(j % i == 0)
4.         for(k = 0; k < j;k++)
5.            sum++;

总频率计数和运行时间（Big-Oh 表示法）是多少？

频率计数检查一段代码并预测要执行的指令数量（例如，对于每条指令，预测代码运行时每条指令会遇到多少次。）

我尝试通过以下方式进行分析：

Loop1执行n-1次，则FC为2n
Loop2执行了(ii)-1次，则FC为3(ii)
Loop1+loop2 的总频率计数为 2n + sum (从 i=1 到 n-1)3*i*i
我对 if(j%i==0) 有疑问。这里的循环执行是什么？
Loop4执行j次，则FC为2j+2

原文

I have the following code snippet:

1. for (i = 1; i < n; i++) 
2.    for (j = 1; j < i*i; j++) 
3.      if(j % i == 0)
4.         for(k = 0; k < j;k++)
5.            sum++;

What is total frequency count and running time (Big-Oh notation)?

Frequency count examine a piece code and predict the number of instructions to be executed (e.g. for each instruction predict how many times each will be encountered as the code runs.)

I try to analyse in the following way:

Loop1 is executed n-1 times, then F.C. is 2n
Loop2 is executed (ii)-1 times, then F.C. is 3(ii)
total frequency count for loop1+loop2 is 2n + sum (from i=1 to n-1)3*i*i
I have a problem with if(j%i==0). What is loop execution here?
Loop4 is executed j times, then F.C. is 2j+2

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

凉城凉梦凉人心 2024-08-29 06:34:03

前 2 行（i 和 j 循环）是 n^3。

第4行，第k个循环是n^2。我很想将它们相乘并表示 n^5。但你必须考虑第 3 行的 if 。

if 语句仅在每 i 次迭代中为真一次，因此您必须除以 i（即除以 n）：(n^3)/n = n^2 给出 n^2 * n^2 = n^4。

O(n^4)

回复收藏 0 原文

滥情空心 2024-08-29 06:34:03

让我们尝试一种实验方法，而不是严格的数学方法。我有心情去玩玩。使用java：

    int n = 5;  long prevSum=0;
    while (n <= 320) {
         long sum = 0;
         n *= 2;

         // insert original code here   

         System.out.printf("n = %d  sum = %d", n, sum);
         if (prevSum > 0) {
             System.out.printf(" ratio %f", ((double)sum) / ((double)prevSum) ); 
         }
         System.out.println();
         prevSum = sum;
    }

输出为：

n = 10  sum = 870
n = 20  sum = 16815 ratio 19.327586
n = 40  sum = 293930 ratio 17.480226
n = 80  sum = 4909060 ratio 16.701460
n = 160  sum = 80222920 ratio 16.341809
n = 320  sum = 1297105040 ratio 16.168759
n = 640  sum = 20862446880 ratio 16.083853

当n加倍时，总和乘以约19.3。当 n 为 40 时，总和为 293930，比率为 17.48 (293930 / 16815 = 17.48)。随着 n 增加，比率接近 16。由于 2^4 = 16，答案是 O(n^4)。顺便说一句，最后一行需要很长时间来计算。

O(n^4)

Let's try an experimental approach, as opposed to a rigorous, mathematical one. I'm in a mood to play around. Using java:

    int n = 5;  long prevSum=0;
    while (n <= 320) {
         long sum = 0;
         n *= 2;

         // insert original code here   

         System.out.printf("n = %d  sum = %d", n, sum);
         if (prevSum > 0) {
             System.out.printf(" ratio %f", ((double)sum) / ((double)prevSum) ); 
         }
         System.out.println();
         prevSum = sum;
    }

The output is:

n = 10  sum = 870
n = 20  sum = 16815 ratio 19.327586
n = 40  sum = 293930 ratio 17.480226
n = 80  sum = 4909060 ratio 16.701460
n = 160  sum = 80222920 ratio 16.341809
n = 320  sum = 1297105040 ratio 16.168759
n = 640  sum = 20862446880 ratio 16.083853

When n is doubled sum is multiplied by about 19.3. When n is 40 sum is 293930, a ratio of 17.48 (293930 / 16815 = 17.48). As n increases the ratio approaches 16. Since 2^4 = 16 the answer is O(n^4). btw, the last line takes a long time to compute.

O(n^4)

回复收藏 0 原文

超可爱的懒熊 2024-08-29 06:34:03

这里有一些可疑的地方：

1. for (i = 1; i < n; i++) 
2.    for (j = 1; j < i*i; j++)      // <-- These two lines.
3.      if(j%i==0)                   // <-- 
4.         for(k=0; k<j;k++)
5.            sum++;

既然我们只在 j 是 i 的倍数时执行循环体，为什么不计入 i：

1. for (i = 1; i < n; i++) 
2.    for (j = i; j < i*i; j += i) 
3.        for(k=0; k<j;k++)
4.            sum++;

这是 O(n^4)

查看你的原始算法。前 2 行的工作时间复杂度为 O(n^3)。然后 O(n^2) 的时间，(j%i == 0)，我们做了 O(n^2) 多的工作。所以上面的算法是O(n^4)。

There's something fishy here:

1. for (i = 1; i < n; i++) 
2.    for (j = 1; j < i*i; j++)      // <-- These two lines.
3.      if(j%i==0)                   // <-- 
4.         for(k=0; k<j;k++)
5.            sum++;

Since We're only executing the loop body when j is a multiple of i, why not count in i's:

1. for (i = 1; i < n; i++) 
2.    for (j = i; j < i*i; j += i) 
3.        for(k=0; k<j;k++)
4.            sum++;

Which is O(n^4)

Looking at your original algorithm. The first 2 lines do O(n^3) work. Then O(n^2) of the time, (j%i == 0), we do O(n^2) more work. So The algorithm above is O(n^4).

回复收藏 0 原文