多参数方法的大O分析 [英] Big O analysis for method with multiple parameters

问题描述

我们正在计算机科学入门课程中学习效率分析，但我无法解决此问题.

假设我有一个方法:

public static void foo(int[][] arr, int num1, int num2) {
   for (int i=0;i<arr.length;i++) {
     arr[0][i] = num1*i;
   }

   for (int j=0;j<arr.length;j++) {
     arr[i][0] = num2*i
   } 
}

我的第一个问题是，如果我有一个方法，其中有3个for循环，但它们不是嵌套的，增长率将是多少?

此外，对于这种特殊的组合方法，此方法的输入大小是否为数组的面积?因为每个for循环从i = 0到i =数组的大小

最后，如果

public static void fee(int[][] arr, double num1, double num2) {
  num1=num1*Math.random();
  while (num1 == 0) {
    num1=num1*Math.random();
  }
   for (int i=0;i<num1;i++) {
     //do something with arr
   }

  num2=num2*Math.random();
  while (num2 == 0) {
    num2=num2*Math.random();
  }
   for (int j=0;j<num2;j++) {
     //do something with arr
   } 
}

我该如何去寻找Big-O分析?

谢谢，我已经阅读了很多有关寻找大O的资源，但我仍然感到困惑.

解决方案

在第一个示例中，您有3个非嵌套的for循环(或实际上是任何一种循环)，它只是O(x + y + z )，其中x，y和z是每个for循环的重复次数(假定内部恒定时间).但是，只有在我们不知道哪个数字最大时，此加号才重要.例如，如果我们知道x> y和x> z，我们可以简单地说算法是O(x)(换句话说，我们知道它与x + y + z成线性关系，但是如果不这样做，因为不知道x，y和z中的哪一个是最重要的因素，所以我们不能简单地说出O(x).简单地说，嵌套=乘，而不是nested =加

在第二个示例中，涉及随机数.就像irrelephant在下面的评论中指出的那样，非正式地，在您提供的示例中它是O(infinity)(但是，我将假设您的意思是while num2 != 0，因为如果num2 = 0，则另一个将无限循环，否则将不执行任何操作) ).但是，大O是最坏的情况.对于随机数，最简单的方法是简单地计算平均时间复杂度.关于时间复杂度的好处是，如果您计算的结果比实际情况稍差一些，那就没人管了.

TLDR:平均时间复杂度约为1000 + log_2 n，其中n为num2.

注意:尽管我们通常在时间复杂度计算中不包括常数因子，但是当它们变得足够大(例如1000)时，它们可能成为最重要的因子，尤其是当n <2 ^ 1000.

详细说明: 因此，我们将采用0.5作为平均乘数(尽管实际上稍差一些).每除以2要么减去尾数一位，要么从指数中减去1.尾数的位长度<<指数，所以让我们只考虑指数.指数具有2 ^ 11的值，但是一半是正的，我们只想取负的，所以2 ^ 10〜=1000.为了首先将其取为1，将需要log2 n，因此答案= 1000 + log2 n

We're learning efficiency analysis in our intro to computer science class and I'm having trouble solving this problem.

Suppose I have a method:

public static void foo(int[][] arr, int num1, int num2) {
   for (int i=0;i<arr.length;i++) {
     arr[0][i] = num1*i;
   }

   for (int j=0;j<arr.length;j++) {
     arr[i][0] = num2*i
   } 
}

My first question is if I have a method where there are 3 for-loops, but they are NOT nested, what would the growth rate be?

Also, for this particular made-up method, would the input size for this method be the area of the array? since each for loop goes from i=0 to i= size of array

And finally, if

public static void fee(int[][] arr, double num1, double num2) {
  num1=num1*Math.random();
  while (num1 == 0) {
    num1=num1*Math.random();
  }
   for (int i=0;i<num1;i++) {
     //do something with arr
   }

  num2=num2*Math.random();
  while (num2 == 0) {
    num2=num2*Math.random();
  }
   for (int j=0;j<num2;j++) {
     //do something with arr
   } 
}

How would I go about finding Big-O analysis?

Thanks, I've read multiple resources on finding big-O, but I am still confused.

解决方案

In the first example, where you have 3 non nested for loops (or any kind of loop really), it would simply be O(x + y + z), where x, y, and z are the amount of repetitions of each for loop (assuming constant time inside). However, this plus is only important if we don't know which of the numbers is going to be the biggest. If we know, for example, that x > y and x > z, we could simply say that the algorithm is O(x) (in other words, we know it is linear to x+y+z, but if we don't know which of x, y, and z is the most significant factor, so we can't simply say O(x). Put simply, nested=multiply, not nested=add

In the second example, random numbers are involved. As irrelephant has stated in the comment below, informally, it is O(infinity) in the example you provided (however, I will make the assumption that you meant while num2 != 0 because the other will infinite loop if num2=0 and do nothing otherwise). However, big O is worst case. For random numbers, it is easiest to simply calculate the average time complexity. The nice thing about time complexity is if you calculate slightly worse than it will actually be, no-one cares.

TLDR: average time complexity is around 1000 + log_2 n, where n is num2.

NOTE: although we don't usually include constant factors in our time complexity calculations, when they get large enough, such as 1000, they can become the most significant factor, especially as it is likely that n << 2^1000.

Long explanation: Hence, we will take 0.5 as the average multiplier (although it is actually slightly worse). Each division by 2 either takes 1 bit off the mantissa, or subtracts 1 from the exponent. bit length of mantissa << exponent, so lets consider only exponent. Exponent has 2^11 values, but half are positive and we only want negative, so 2^10 ~= 1000. In order to get it to one in the first place it will take log2 n, so answer = 1000 + log2 n

这篇关于多参数方法的大O分析的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！