计算原始运算计算Big-O表示法 [英] Counting Primitive Operations & Calculating Big-O Notation

问题描述

我编写了一段Java代码，当给定一个数组(arrayX)时，它计算出该数组的前缀平均值并将其输出到另一个数组(arrayA)中.我应该计算原始操作并计算Big-O表示法(我猜这是计算的总数).我已经包括了Java代码以及我认为每行旁边的原始操作数，但是我不确定是否正确地计算了它们.在此先感谢并感谢您的经验，我觉得这很难理解:)

  double [] arrayA =新的double [arrayX.length];*(3次操作)*for(int i = 0; i< arrayX.length; ++ i)*(4n + 2个运算)*{双和= arrayX [i];*(3n次操作)*for(int j = 0; j< i; ++ j)*(4n ^ 2 + 2n次运算)*{sum = sum + arrayX [j];*(5n ^ 2次操作)*}arrayA [i] = sum/(i + 1);*(6n次操作)*}返回arrayA;*(1次操作)* 

操作总数:9n ^ 2 + 15n + 6

解决方案

我不认为什么构成原始操作"有任何标准定义.我假设这是一个课堂作业；如果您的讲师给了您有关哪些操作可以算作原始操作的详细信息，那么就过去了，否则，只要您有合理的解释，我认为他不会以任何方式指责您.>

关于内循环:

  for(int j = 0; j< i; ++ j) 

请注意，循环执行的总次数不是 n ² ，而是0 + 1 + 2 + ... +( n -1)= n ( n -1)/2.因此，您的计算可能不正确.

Big-O表示法并不是真正的计算总数"；粗略地说，这是一种估算 n 增长时计算数量如何增长的方式，方法是说计算数量与 n 的某些函数大致成比例.如果对于任何常数 K ，计算数量为 Kn ² ，我们说计算数量为 O(n ² )不管常量 K 是多少.因此，算作原始操作并不完全无关紧要.您可能会得到9 n ² ，其他计算不同操作的人可能会得到7 n ² 或3 n ² ，但这没关系-都是 O(n ² ).而且低阶项(15 n +6)根本不算，因为它们的增长比 Kn ² 项慢.因此，它们与确定适当的big-O公式无关.

I've written a piece of java code that when given an array (arrayX), works out the prefix averages of that array and outputs them in another array (arrayA). I am supposed to count the primitive operations and calculate the Big-O notation (which i'm guessing is the overall number of calculations). I have included the java code and what I believe to be the number of primitive operations next to each line, but I am unsure whether I have counted them correctly. Thanks in advance and sorry for my inexperience, i'm finding this hard to grasp :)

double [] arrayA = new double [arrayX.length]; *(3 Operations)*

    for (int i = 0; i < arrayX.length; ++i) *(4n + 2 Operations)* 
    {
        double sum = arrayX[i]; *(3n Operations)*

        for (int j = 0; j < i; ++j) *(4n^2 + 2n Operations)*
        {
            sum = sum + arrayX[j]; *(5n^2 Operations)*
        }
        arrayA[i] = sum/(i+1); *(6n Operations)*
    }
    return arrayA; *(1 Operation)*

Total number of operations: 9n^2 +15n + 6

解决方案

I don't think there's any standard definition of "what constitutes a primitive operation". I'm assuming this is a class assignment; if your instructor has given you detailed information about what operations to count as primitive operations, then go by that, otherwise I don't think he can fault you for any way you count them, as long as you have a reasonable explanation.

Regarding the inner loop:

for (int j = 0; j < i; ++j)

please note that the total number of times the loop executes is not n², but rather 0+1+2+...+(n-1) = n(n-1)/2. So your calculations are probably incorrect there.

Big-O notation is not really "the total number of calculations"; roughly speaking, it's a way of estimating how the number of calculations grows when n grows, by saying that the number of calculations is roughly proportional to some function of n. If the number of calculations is Kn² for any constant K, we say that the number of calculations is O(n²) regardless of what the constant K is. Therefore, it doesn't completely matter what you count as primitive operations. You might get 9n², someone else who counts different operations may get 7n² or 3n², but it doesn't matter--it's all O(n²). And the lower-degree terms (15n+6) don't count at all, since they grow more slowly than the Kn² term. Thus they aren't relevant to determining the appropriate big-O formula.

这篇关于计算原始运算计算Big-O表示法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！