我刚刚尝试用各种方法实现代码(用 Java 编写)，通过这些方法可以计算斐波那契数列的第 n 项，我希望能验证我所学的内容。
迭代实现如下:
public int iterativeFibonacci(int n)
{
if ( n == 1 ) return 0;
else if ( n == 2 ) return 1;
int i = 0, j = 1, sum = 0;
for ( ; (n-2) != 0; --n )
{
sum = i + j;
i = j;
j = sum;
}
return sum;
}
递归实现如下:-
public int recursiveFibonacci(int n)
{
if ( n == 1 ) return 0;
else if ( n == 2 ) return 1;
return recursiveFibonacci(n-1) + recursiveFibonacci(n-2);
}
内存的实现如下:-
public int memoizedFibonacci(int n)
{
if ( n <= 0 ) return -1;
else if ( n == 1 ) return 0;
else if ( n == 2 ) return 1;
if ( memory[n-1] == 0 )
memory[n-1] = memoizedFibonacci(n-1);
if ( memory[n-2] == 0 )
memory[n-2] = memoizedFibonacci(n-2);
return memory[n-1]+memory[n-2];
}
在尝试找出这些实现的 Big-O 时，我有点怀疑。我相信迭代实现是 O(n)，因为它循环了 N-2 次。
在递归函数中，有重新计算的值，因此我认为它是O(n^2)。
在 memoized 函数中，超过一半的值是基于 memoization 访问的。我读过一个算法是O(log N)，如果它需要恒定的时间来将问题空间减少一个分数，而一个算法是O(N)，如果它需要恒定的时间以恒定的量减少问题空间。我是否相信 memoized 实现的复杂性是 O(n)？如果是这样，迭代实现不是三者中最好的吗？ (因为它不使用内存所需的额外内存)。
最佳答案
递归版本不是多项式时间 - 它是指数的，tightly bounded at φn其中 φ 是黄金比例 (≈ 1.618034)。递归版本将使用 O(n) 内存(使用来自堆栈)。
记忆化版本在第一次运行时将花费 O(n) 时间，因为每个数字只计算一次。但是，作为交换，您当前的实现也需要 O(n) 内存(n 来自存储计算值，以及对于第一次运行的堆栈)。如果你多次运行它，时间复杂度将变为 O(M + q) 其中 M 是max of all input n 和 q 是查询的数量。内存复杂度将变为 O(M)，它来自包含所有计算值的数组。
如果您考虑一次运行，迭代实现是最好的，因为它也在 O(n) 中运行，但使用恒定量的内存 O(1) 来计算。对于大量运行，它会重新计算所有内容，因此它的性能可能不如 memoization 版本。
(但是，实际上，早在性能和内存问题之前，即使是 64 位整数，数字也可能溢出，因此准确的分析必须考虑到在计算时进行加法所需的时间完整的数字)。
正如 plesiv 所提到的，斐波那契数也可以通过矩阵乘法以 O(log n) 计算(使用与快速求幂相同的技巧，将指数减半每一步)。
关于java - Big-O 用于各种斐波那契实现，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/13440020/
大约一年前，我决定确保每个包含非唯一文本的Flash通知都将从模块中的方法中获取文本。我这样做的最初原因是为了避免一遍又一遍地输入相同的字符串。如果我想更改措辞，我可以在一个地方轻松完成，而且一遍又一遍地重复同一件事而出现拼写错误的可能性也会降低。我最终得到的是这样的:moduleMessagesdefformat_error_messages(errors)errors.map{|attribute,message|"Error:#{attribute.to_s.titleize}#{message}."}enddeferror_message_could_not_find(obje
我真的很习惯使用Ruby编写以下代码:my_hash={}my_hash['test']=1Java中对应的数据结构是什么？ 最佳答案 HashMapmap=newHashMap();map.put("test",1);我假设？ 关于java-等价于Java中的RubyHash，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/22737685/
我有一个用户工厂。我希望默认情况下确认用户。但是鉴于unconfirmed特征，我不希望它们被确认。虽然我有一个基于实现细节而不是抽象的工作实现，但我想知道如何正确地做到这一点。factory:userdoafter(:create)do|user,evaluator|#unwantedimplementationdetailshereunlessFactoryGirl.factories[:user].defined_traits.map(&:name).include?(:unconfirmed)user.confirm!endendtrait:unconfirmeddoenden
我已经在Sinatra上创建了应用程序，它代表了一个简单的API。我想在生产和开发上进行部署。我想在部署时选择，是开发还是生产，一些方法的逻辑应该改变，这取决于部署类型。是否有任何想法，如何完成以及解决此问题的一些示例。例子:我有代码get'/api/test'doreturn"Itisdev"end但是在部署到生产环境之后我想在运行/api/test之后看到ItisPROD如何实现？ 最佳答案 根据SinatraDocumentation:EnvironmentscanbesetthroughtheRACK_ENVenvironm
我正在尝试使用boilerpipe来自JRuby。我看过guide从JRuby调用Java，并成功地将它与另一个Java包一起使用，但无法弄清楚为什么同样的东西不能用于boilerpipe。我正在尝试基本上从JRuby中执行与此Java等效的操作:URLurl=newURL("http://www.example.com/some-location/index.html");Stringtext=ArticleExtractor.INSTANCE.getText(url);在JRuby中试过这个:require'java'url=java.net.URL.new("http://www
给定一个复杂的对象层次结构，幸运的是它不包含循环引用，我如何实现支持各种格式的序列化？我不是来讨论实际实现的。相反，我正在寻找可能会派上用场的设计模式提示。更准确地说:我正在使用Ruby，我想解析XML和JSON数据以构建复杂的对象层次结构。此外，应该可以将该层次结构序列化为JSON、XML和可能的HTML。我可以为此使用Builder模式吗？在任何提到的情况下，我都有某种结构化数据-无论是在内存中还是文本中-我想用它来构建其他东西。我认为将序列化逻辑与实际业务逻辑分开会很好，这样我以后就可以轻松支持多种XML格式。 最佳答案 我最
当我使用has_one时，它工作得很好，但在has_many上却不行。在这里您可以看到object_id不同，因为它运行了另一个SQL来再次获取它。ruby-1.9.2-p290:001>e=Employee.create(name:'rafael',active:false)ruby-1.9.2-p290:002>b=Badge.create(number:1,employee:e)ruby-1.9.2-p290:003>a=Address.create(street:"123MarketSt",city:"SanDiego",employee:e)ruby-1.9.2-p290
我只想对我一直在思考的这个问题有其他意见，例如我有classuser_controller和classuserclassUserattr_accessor:name,:usernameendclassUserController//dosomethingaboutanythingaboutusersend问题是我的User类中是否应该有逻辑user=User.newuser.do_something(user1)oritshouldbeuser_controller=UserController.newuser_controller.do_something(user1,user2)我
什么是ruby的rack或python的Java的wsgi？还有一个路由库。 最佳答案 来自Python标准PEP333:Bycontrast,althoughJavahasjustasmanywebapplicationframeworksavailable,Java's"servlet"APImakesitpossibleforapplicationswrittenwithanyJavawebapplicationframeworktoruninanywebserverthatsupportstheservletAPI.ht
华为OD机试题本篇题目：明明的随机数题目输入描述输出描述：示例1输入输出说明代码编写思路最近更新的博客华为od2023|什么是华为od，od薪资待遇，od机试题清单华为OD机试真题大全，用Python解华为机试题|机试宝典【华为OD机试】全流程解析+经验分享,题型分享,防作弊指南华为o