2

我有以下算法来确定两个数字 x 和 y 的最大公约数。我需要找到描述该算法的大符号并解释原因,但我不知道如何做到这一点。

有人可以看看我的代码并解释它是什么类型的大哦符号吗?

     public void question1(int x, int y){
            ArrayList divisorx = new ArrayList(); //the list of divisors of number x
            ArrayList divisory = new ArrayList();//divisors of number y
            ArrayList answerSet = new ArrayList();//the common divisors from both   
            //divisorx and divisory

            for(int i=1; i<=x; i++){//this loop finds the divisors of number x and 
                                    //adds them to divisorx
                    double remainder = x%i;
                    if(remainder==0){
                        //i is a divisor
                        divisorx.add(i);
                    }
            }
            for(int i2=1; i2<=y; i2++){//this loop finds the divisors of number y 
                                       //and adds them to divisory
                    double remainder2 = y%i2;
                    if(remainder2==0){
                        //i2 is a divisor
                        divisory.add(i2);
                    }
            }
      int xsize = divisorx.size();
      int ysize = divisory.size();

            for(int i=0; i<xsize; i++){//this massive loop compares each element of 
        //divisorx to those of divisory to find common divisors. It adds those common
        //divisors to the arraylist answerSet
               for(int j=0; j<ysize; j++){
                   if(divisorx.get(i)==divisory.get(j)){
                       //common divisor has been found
                       //add it to an answer array

                       answerSet.add(divisorx.get(i));

                   }
                }
            }
    Collections.sort(answerSet);//sorts the answerSet from smallest to greatest

    Object gcd = answerSet.get(answerSet.size()-1);//get the last element of the
                                                   //arraylist, which is the gcd       
    System.out.print("Your Answer: "+gcd);//print out the greatest common divisor
 }
4

3 回答 3

2

前两个循环的成本分别为O(X)O(Y)

N 的除数是 O(sqrt(N))(见注释),所以 xsize 和 ysize 是 O(sqrt(X)) 和 O(sqrt(Y))。

因此,您的最后一个循环花费了O(sqrt(X).sqrt(Y))

answerSet大小为 O(min(sqrt(X),sqrt(Y))),因为它是 和 的divisorx交集divisory

您对 answerSet 执行排序,即O(min(sqrt(X),sqrt(Y)) log(min(sqrt(X),sqrt(Y)))

所有这些都是 O(X+Y),所以总复杂度是O(X+Y)

于 2013-01-10T21:28:57.187 回答
1

最大的复杂性是您拥有的两个嵌套 for 循环大 O顺序,意味着它是相对于输入大小的复杂性。在这里,您的输入大小是您在线性时间(每个 1 个 for 循环)中找到的除数数,意思是n + nO(n)。您示例中的排序通常具有n*log(n). 您的嵌套 for 循环是方形含义O(n^2)。那么你的订单就是O(n^2)因为这是计算中最大的复杂性。我们在多项式表达式中取最大次数,将所有复杂性相加,因此O(n^2 + n*log(n) + 2n)它是二次多项式,因此是 ~ O(n^2)

需要注意的是,顺序是空间和时间的较大复杂度。因此,如果内存使用复杂度大于计算复杂度,那么就会接管。

于 2013-01-10T21:31:05.133 回答
0

第一个循环准确地完成了X几次。
第二个循环Y时间。
第三个循环肯定少于(X/2 + 1) * (Y/2 + 1)次(因为一个数字最多N可以有N/2 + 1除数)。所以最坏的情况是O(XY/4) = O(XY)
list 的大小相同,answerSet最多可以有XY/4元素。最后排序是在O(nlogn)(根据javadoc)中完成的,也就是说,在你的情况下,O(XYlog(XY)).
所以最终的复杂度是O(X + Y + XY + XYlog(XY)) = O(XYlog(XY))
如果您只想用泛型来表达复杂性N,那么就是O((N^2)logN), where N = max(X, Y)

于 2013-01-10T21:33:39.347 回答