我有一个奇怪的算法,而不是递归调用2次.它的
int alg(int n)
loop body = ?(3n+1)
alg(n-1);
alg(n-2)
不知何故,我需要找到这个算法的复杂性.我试图使用上述方程的特征多项式找到它,但结果系统太难解决所以我想知道是否有任何其他直接方式..
我们必须找到这个系列的第n个术语http://oeis.org/A028859
N <= 10亿
答案应该是模数1000000007
我写了代码,但是当na是巨大的数字时,时间限制超过了.
#include<iostream>
using namespace std
int main()
{
long long int n;
cin>>n;
long long int a,b,c;
a=1;
b=3;
int i;
for(i=3;i<=n;i++)
{
c=(2ll*(a+b))%1000000007;
a=b;
b=c;
}
cout<<c;
}
我的数学背景不太好,这是我尝试编写JAVA代码,其运行时间与不同的输入成比例.
用n ^ 2/3.由于n ^ 2/3 =立方根n*立方根n,因此我可以写
public void test(int n){
for (int i = 0; i*i*i < n; i++) {
for (int j = 0; j*j*j < n; j++) {
count ++;
}
}
}
用4 ^ n.我可以使用Fibonnaci方法吗？
public int fibonnaci(int n) {
if (n <= 1) {
return 1;
} else {
return fibonnaci(n - 2) + fibonnaci(n - 1);
}
}
我可以知道上面的代码是否正确吗？非常感谢!
我有这个功能,想知道时间的复杂性:
int f2(int n) {
if(n<2) return 1;
return f2(n/2)+f2(n-2);
}
我使用伸缩展开法计算其运行时间为O(n 2).它是否正确？
编辑:重新考虑之后,我发现这个函数有一个类似于mergesort的结构,它具有复杂度Θ(n log n).那是对的吗？
我阅读了关于递归斐波那契数列的 Big O 的两篇文章，但仍然没有概念性地理解为什么它是O(2^n)。
这不是此链接的副本。请不要标记为重复。我正在寻找一个概念性的答案。
这是最简单的递归函数之一，我想了解如何看待它并在没有复杂数学和证明的情况下确定大 O。
// O(2^n)
function fiboR(n){
if( n === 0 || n === 1 ){
return n;
} else if ( n >=2 ){
return fiboR(n-1) + fiboR(n-2);
}
}
例如，迭代版本的 Big O 是O(n)。我可以看看，随着 n 的增加，while 循环迭代线性增加。不需要复杂的数学或冗长的证明。
// O(n)
function fibo(n){
let prev0 = 0;
let prev1 = 1;
if( n === 0 || n === 1 ){
return n;
}
while( n-- >= 2){
sum = …我编写了一个代码段来确定图中最长的路径.以下是代码.但由于中间的递归方法,我不知道如何在其中获得计算复杂性.由于找到最长的路径是NP完全问题,我认为它类似于O(n!)或者O(2^n),但我怎么能真正确定它呢？
public static int longestPath(int A) {
int k;
int dist2=0;
int max=0;
visited[A] = true;
for (k = 1; k <= V; ++k) {
if(!visited[k]){
dist2= length[A][k]+longestPath(k);
if(dist2>max){
max=dist2;
}
}
}
visited[A]=false;
return(max);
}
我被告知过
O(2 ^ N)表示一种算法,其增长将随输入数据集中的每个附加元素加倍
有人能提供一个像这样的例子吗？
有人请解释我的斐波那契搜索算法.
我已经尝试了很多资源并进行了大量搜索,但算法仍然不清楚.大多数资源都将其描述为与二进制搜索相关联,但我不理解它们.我知道斐波那契搜索算法是二进制搜索的扩展,我很清楚.
我的书也没能解释.
我知道定义为F(n)= F(n-1)+ F(n-2)的斐波纳契数,所以不需要解释.
通过添加我不理解的内容来更新问题@AnthonyLabarre说:
我正在使用的书有奇怪的符号,没有任何解释.在这里发布算法,请帮忙.
if(key == a[mid]) return mid; // understood this, comes from binary search
if(key > a[mid]) {
if(p == 1) return -1; // What is p? It comes as a function arg
mid = mid + q; //Now what's this q? Again comes a function arg
p = p - q; // Commented as p=fib(k-4)
q = q-p; // q = fib(k-5)
} else // key < a[mid] {
if(q == 0) return …这是来自"算法的介绍"的问题,其编号为4.4-5并且描述如下:
使用递归树确定递推T(n)= T(n-1)+ T(n/2)+ n的良好渐近上界.使用替换方法验证您的答案.
我发现计算递归树的重复是很困难的.我给出的答案
Math.pow(2,n)的
看起来太松了.也许有更好的猜测存在.谢谢你的帮助.
计算以下递归函数的时间和空间复杂度(Big O表示法)的最直观方法是什么？
function count(str) {
if (str.length <= 1) {
return 1;
}
var firstTwoDigits = parseInt(str.slice(0, 2), 10);
if (firstTwoDigits <= 26) {
return count(str.slice(1)) +
count(str.slice(2));
}
return count(str.slice(1));
}