斐波那契通项公式

斐波那契数列

http://www.nowcoder.com/questionTerminal/c6c7742f5ba7442aada113136ddea0c3

O(1)通项公式解法:

public class Solution {
    public int Fibonacci(int n) {
        double a = Math.sqrt(5.0);
        double temp1 = (1.0 + a)/2.0;
        double temp2 = (1.0 - a)/2.0;
        return (int)(1.0/a*(Math.pow(temp1, n) - Math.pow(temp2, n)));
    }
}
全部评论
严格来说不算O(1),使用快速幂的次方运算复杂度为O(logn)
点赞 回复 分享
发布于 2020-07-18 17:20

相关推荐

10-02 19:29
已编辑
浙江科技大学 运营
职场水母:等春招吧,春招才是双非的主战场,放心吧佬,实习很好,肯定能进大厂的
简历被挂麻了,求建议
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务