小编Moh*_*ssi的帖子

我无法确定Euclid最大公分母算法的时间复杂度.这个伪代码算法是:

function gcd(a, b)
    while b ? 0
       t := b
       b := a mod b
       a := t
    return a

它似乎取决于a和b.我的想法是时间复杂度是O(a%b).那是对的吗？有没有更好的方法来写这个？

在图像中，当对字符串数组进行排序时，我不明白多余的O从何而来。我得到排序的字符串数组将是O（log a），我不明白为什么我们也必须添加O（s）。

在我看来，O（a log a）负责整理字符串数组中的所有字符串。

我有一个程序,并试图计算其复杂性.我想确定我没有弄错

for(int i=4; i<=n; i=i*4)
{
    cout<<"counter for first loop: "<<++count1<<endl;
    for(int j=i;j>=0;j=j-4)
    {
        cout<<"counter for second loop: "<<++count2<<endl;
        for(int k=0;k<=n;k++)
        {
            cout<<"counter for third loop: "<<++count3<<endl;
        }
    }
}

这里,第三个循环的复杂度是O(n),然后与第二个循环一起,复杂度变为O(n.log ₄ i),整个程序的复杂度为O(n.(log ₄ i)²) .我的回答是对的？谢谢

找到第一个'n'素数的算法是:

while (number <= n) {
  boolean isPrime = true; 
  for (int divisor = 2; divisor <= (int)(Math.sqrt(number)); divisor++) {
    if (number % divisor == 0) {
      isPrime = false;      
      break;
    }
  }
  if(isPrime) 
    System.out.print(number + " ");
}

这本书"Java编程简介"计算了这个算法的big-O:

由于在for循环中需要√i步骤来检查数字i是否为素数,因此算法采用√2+√3+√4+ ... +√n步骤来找到小于或等于n的所有素数.

观察,

√2+√3+√4+ ... +√n<=n√n

因此,该算法的时间复杂度为O(n√n).

阙:

1.他说,"它需要√i中的步骤for循环,以检查是否数字我是总理".

你不认为它应该是(√i-1)步骤.

2.请解释

√2+√3+√4+ ... +√n<=n√n

(我知道如果你用随机数替换'n',这种关系就成立了.我需要解释)

 sum = 0;
 for (i = 1; i <= n; i++) {    //#1
   for (j = 1; j <= i * i; j++) {     //#2
      if (j % i == 0) {    //#3 
          for (k = 1; k <= j; k++) {   //#4
             sum++;
         }
     }
  } 

}

以上让我感到困惑

Suppose #1 runs for N times
    #2 runs for N^2 times
    #3 runs for  N/c since for N inputs N/c could be true conditions
    #4 runs for  N times

因此大致我可以看O(N ^ …

假设我们有一个类Animal,子类为cat,eagle

现在我有一个方法:

public void process(Animal animal) {

   if (animal instanceof Cat) {
     if (!animal.meow()) {
        throw exception("cat does not meow");
     } else {
      animal.feedFish();
     }
   }

   if (animal instanceof eagle) {
      if (!animal.fly()) {
         throw exception("eagle does not fly");
      } else {
        animal.checkMaxFlightAltitude();
      }
   }
}

这里的猫有2种方法meow和feedfish这比鹰的方法完全不同fly,并checkmaxflight

大多数设计模式都围绕着假设,即子类有一个常见的方法,比如draw()由circle draw和square 继承的Shapedraw

1. 有没有办法对子类进行验证,例如没有instanceof检查的猫和老鹰？

2. 任何好的设计模式(假设子类不共享基类中的方法？)

我有一个带有两个嵌套for循环的递归算法.我想弄清楚Big-O的时间复杂度是多少.

public Set<Person> getDistinctCombinedPersons(Collection<Person> persons) {
  return permutatePersons(new ArrayList(persons), new HashSet<>(persons));
}

private Set<Person> permutatePersons(List<Person> personList, Set<Person> personSet) {
  if(personList.isEmpty() {
    return personSet;
  }

  Set<Person> deepCopyPersonSet = new HashSet<>(personSet);

  for(Person lPerson : personList) {
    for(Person sPerson : deepCopyPersonSet) {
      Person uniquePerson = CombinePeople.combine(lPerson, sPerson);
      personSet.add(uniquePerson);
    }
  }

  personList.remove(personList.size()-1);

  return permutatePersons(personList, personSet);
}

我只能找到关于如何递归和迭代地实现gcd函数的帖子,但是我找不到这个.我确定它在Stackoverflow上然而我找不到它所以我道歉如果它是一个重复的帖子.

我查看了维基百科(这里)的分析,无法理解它们的递归关系.

考虑以下在C中递归实现的GCD函数的实现.它具有一个前提条件,即两个数字必须为正数,但与运行时间无关.

int gcd( int const a, int const b ) {
  // Checks pre conditions.
  assert( a >= 0 );
  assert( b >= 0 );

  if ( a < b ) return gcd( b, a );

  if ( b == 0 ) return a;

  return gcd( b, a % b );
}

对运行时间进行分析我发现每个操作都是O(1),因此我们知道到目前为止的递归关系是:T(n)= O(1)+ ???.现在分析递归调用,我不知道如何将(mod b)解释为我的递归调用以正确陈述我的递归关系.

bigO中以下算法的运行时间是多少？

for(int i=1;i<=n;i++){
    for(int j=i;j<=n;j++){
        for(int k=j; k<=n;k++){
            for(int l=k; l<=n;l++){

                ...

            }
        }
    }
}