Alan's Notebook🦍
  • home🧀
  • about🥤
  • categories🥪
  • tags🍨
  • archives🍯
  • friend links🍻
  • Search

时间复杂度O(log(n))空间复杂度O(1)求斐波那契数列第n项

Posted on 2019-05-13 | Edited on 2019-06-05 | In algorithm

斐波那契数的计算方式是:
$$
fib(n)=\left\{\begin{matrix}
0 & n=0\\
1 & n=1\\
fib(n-1)+fib(n-2) & n\geq 2 \\
\end{matrix}\right.
$$
之前用这个计算公式写出了时间复杂度O(n)空间复杂度O(1)的动态规划迭代算法。而这篇文章主要是讲讲时间复杂度O(log(n))空间复杂度O(1)算法的思路。本文代码都已反复测试过,确保可以正常运行。

前两个代码可以求得:
$$
fib(n) \quad \forall n \in \{x|0 \leq x \leq 93\}
$$

  • 最后的迭代思路代码不可以计算fib(0)​;
  • 最大只可以求得fib(93)​,这是因为unsigned long long类型的存储限制,数据再大会溢出。
Read more »

华为笔试题 路径搜索

Posted on 2019-05-10 | Edited on 2019-05-15 | In algorithm

华为笔试题。感觉考DFS的使用。

  • 更新:今天被美能华面试官提醒,dfs的判断语句可以写在函数开头,进入的时候再进行判断,这样程序会更简洁。
Read more »

华为笔试题 括号展开

Posted on 2019-05-09 | Edited on 2019-05-10 | In algorithm

华为笔试题。将括号里的内容按一定规则展开,感觉考查字符串处理和栈的使用。

Read more »

分布式与云计算复习笔记

Posted on 2019-04-07 | Edited on 2019-04-25 | In distributed system

分布式与云计算2019春季课程笔记

这个东西吧,太简单了,我们这里不讲了

这个东西吧,比较难,后续我们在讲吧(后续后续。。。)

这里吧,(喝口水,ppt翻页),直接跳过了

天文地理鲁迅balabala,石竹老师先退票再买票,最后没抢到票我感到非常高兴233333

end

Read more »

分布式lab3:词频统计

Posted on 2019-04-07 | Edited on 2019-04-20 | In distributed system

使用hadoop写一次词频统计的demo。

Read more »

分布式lab2:Hadoop Distributed File System(HDFS)上的基本操作

Posted on 2019-03-30 | Edited on 2019-04-03 | In distributed system

分布式第二次实验。

Read more »

分布式lab1:Ubuntu16.04上Hadoop环境安装

Posted on 2019-03-29 | Edited on 2019-04-14 | In distributed system

分布式第一次实验,怎么坑这么多!🤯

Read more »

round(number[, ndigits])

Posted on 2019-01-15 | Edited on 2019-04-03 | In note

round函数是Python中常用的四舍五入的函数,但是今天试用了一下发现有点小坑。

Read more »

科大软院 - 人工智能期末考试复习

Posted on 2018-12-16 | Edited on 2019-04-17 | In deep learning

但愿看我博客复习的同学不会被8%的概率dropout吧~

Read more »

删数问题的贪心选择策略证明

Posted on 2018-12-11 | Edited on 2019-05-26 | In algorithm

题目:在一个n位的正整数A[1…n]中删除其中任意k(k≤n)个数字后,剩下的数字按原次序组成一个新的正整数。对于给定的n位正整数A和k,设计一个贪心算法,使得剩下的数字组成的新数最小。
如:A=278693,k=4时最小新数为23,k=3时为263

Read more »
12
Alan Ke

Alan Ke

Have a nice coding!🍻
15 posts
5 categories
24 tags
GitHub E-Mail
© 2018 – 2019 Alan Ke