相关疑难解决方法(0)

我理解Big-O表示法,但我不知道如何为许多函数计算它.特别是,我一直试图弄清楚Fibonacci序列的幼稚版本的计算复杂性:

int Fibonacci(int n)
{
    if (n <= 1)
        return n;
    else
        return Fibonacci(n - 1) + Fibonacci(n - 2);
}

Fibonacci序列的计算复杂度是多少以及如何计算？

我正在学习算法分析.我理解算法运行时最差的概念.

但是,算法的最坏情况运行时间的上限和下限是多少？

有什么可以一个例子,其中一个上限用于运行算法的时间的最坏情况是从不同下界用于运行相同的算法的时间的最坏情况？

我有一个使用递归打印斐波纳契数列的程序.有更好的方法,但我被要求使用递归,所以我必须这样做.

这是程序:

#include <stdio.h>
#define TERMS 10

long fibo(int);

int main(void){
   for(int i = 1; i <= TERMS; i++) {
       printf("%ld", fibo(i));
   }
   return 0;
}

long fibo(int n){
    if (n < 3) {
        return 1;
    }
    else {
        return fibo(n - 1) + fibo(n - 2);
    }
}

我知道这对于Fibonacci系列来说真的是一个糟糕的方法,从上面可以清楚地看到,因为TERMS超过35,该程序需要花费大量时间才能完成.

我已经完成了这个答案,无法理解他们是如何解决的,但它看起来像

fibo(int n)的时间复杂度为O(2 ^ n)

我可能也完全错了,但我想要的只是:

这个完整程序的时间复杂度是什么,简要解释一下你如何计算它？

如果你有一个更好的方法来计算使用递归计算Fibonacci,也欢迎.

我遇到了一个挑战,要在java中制作一个算法来计算一个字符串形式可能有多少DNA链.字符串可以包含这5个字符(A,G,C,T,？)

？在字符串中可以是(A,G,C或T)但是？可能不会导致字符串中的一对.例如,在这个字符串"A？G" ？可能只有C或T.可以有无限的问号对,因为它们最后都是字符.

功能形式就是这个

public static int chains(String base) {
    // return the amount of chains
}

如果基本字符串是"A？C？" 可能的组合是6 =(AGCA,AGCG,AGCT,ATCA,ATCG,ATCT)

案件 (??? - 36)(AGAG - 1)(A ??? T - 20)

(？ - 4)(A？ - 3)(？A - 3)(?? - 12)(A？A - 3)(A？C - 2)...

给定基数(pohja)字符串的最大长度为10!

标准: 1.连续两个字符的组合是非法组合,因此不计算.

到目前为止我所拥有的:

    public static int chains(String pohja) {
    int sum = 1;
    int length = pohja.length();
    char[] arr = pohja.toCharArray();
    int questionMarks = …

我很难证明斐波那契的"坏"版本是O(2 ^ n).IE浏览器.鉴于功能

int fib(int x)
{
  if ( x == 1 || x == 2 )
  {
    return 1;
  }
  else
  {
    return ( f( x - 1 ) + f( x - 2) );
  }
}

我可以得到帮助证明这是O(2 ^ n).