b*********n
发帖数: 1258 | 1 Fibonacci序列的Recursive的那个算法
我回答 O(N)
好像不对呀 |
g*******y
发帖数: 1930 | 2 算单个的F(n)?
algorithmics以前给过一个很好的logN的方法算单个的F(n)
【在 b*********n 的大作中提到】
: Fibonacci序列的Recursive的那个算法
: 我回答 O(N)
: 好像不对呀
|
b*********n
发帖数: 1258 | 3 对，算单个的F(n)
电话面试让我口述recursive算法程序，
然后跟着问我复杂度
我就不是很明白recursive算法的复杂度
【在 g*******y 的大作中提到】
: 算单个的F(n)?
: algorithmics以前给过一个很好的logN的方法算单个的F(n)
|
H*M
发帖数: 1268 | 4 ...
exponential for recursive one
using a dp way, you can get o(n)
using a matrix multiplication way o(lgn)
seems there is also a explicit formular for that, O(1)?
【在 b*********n 的大作中提到】
: 对，算单个的F(n)
: 电话面试让我口述recursive算法程序，
: 然后跟着问我复杂度
: 我就不是很明白recursive算法的复杂度
|
g*******y
发帖数: 1930 | 5 是有通项公式，不过计算那个通项公式，要算某个数的n次方，就是说跟matrix
multiplication其实是一样的复杂度。
【在 H*M 的大作中提到】
: ...
: exponential for recursive one
: using a dp way, you can get o(n)
: using a matrix multiplication way o(lgn)
: seems there is also a explicit formular for that, O(1)?
|
H*M
发帖数: 1268 | 6 yeah yeah. my bad
【在 g*******y 的大作中提到】
: 是有通项公式，不过计算那个通项公式，要算某个数的n次方，就是说跟matrix
: multiplication其实是一样的复杂度。
|
s*******s
发帖数: 1568 | 7 Fib has analytical solution,
the running time for recusion is about o(golden ratio^n)
【在 b*********n 的大作中提到】
: Fibonacci序列的Recursive的那个算法
: 我回答 O(N)
: 好像不对呀
|
m*****f
发帖数: 1243 | 8 算单个F(n)最好的logn方法是利用矩阵乘方, 是算法导论的作者上课的时候给的
http://www.verycd.com/topics/87348/
【在 g*******y 的大作中提到】
: 算单个的F(n)?
: algorithmics以前给过一个很好的logN的方法算单个的F(n)
|
m********0
发帖数: 2717 | 9 theta([(sqrt(5)+1)/2)^n])
matrix : theta(log n)
【在 b*********n 的大作中提到】
: Fibonacci序列的Recursive的那个算法
: 我回答 O(N)
: 好像不对呀
|
m********0
发帖数: 2717 | 10 1 1
1 0
的n次方
就是
f(n+1) f(n)
f(n) f(n-1)
【在 g*******y 的大作中提到】
: 算单个的F(n)?
: algorithmics以前给过一个很好的logN的方法算单个的F(n)
|
|
|
a****n
发帖数: 1887 | |
H****r
发帖数: 2801 | 12 This should be O(1)?
http://en.wikipedia.org/wiki/Fibonacci_number
Computation by rounding
Since \begin{matrix}|1-\varphi|^n/\sqrt 5 < 1/2\end{matrix} for all n\geq 0,
the number F(n) is the closest integer to \varphi^n/\sqrt 5\, . Therefore
it can be found by rounding, or in terms of the floor function:
F(n)=\bigg\lfloor\frac{\varphi^n}{\sqrt 5} + \frac{1}{2}\bigg\rfloor,\ n
\geq 0.
【在 b*********n 的大作中提到】
: Fibonacci序列的Recursive的那个算法
: 我回答 O(N)
: 好像不对呀
|
m********0
发帖数: 2717 | 13 题目问的不是你说的，
问的是recursive的复杂度。
golden ratio ^ n
【在 a****n 的大作中提到】
: O（n） 用两个变量存储fn fn-1
|
g*******y
发帖数: 1930 | 14 算recursive的复杂度，其实跟算fibonacci数本身，几乎是一样的
假设recursive算f(n)的steps是g(n)的话
g(n) = g(n-1) + g(n-2) + O(1)
特征值仍然是 (1 +/- sqrt(5))/2，用算fibonacci通项式的同样方法算出g(n)的通项
式就行了 |
x***y
发帖数: 633 | 15 Can you give some details? thanks..
【在 g*******y 的大作中提到】
: 算单个的F(n)?
: algorithmics以前给过一个很好的logN的方法算单个的F(n)
|
g*******y
发帖数: 1930 | 16 someone already did in her reply... you may wanna read this post more
closely
【在 x***y 的大作中提到】
: Can you give some details? thanks..
|
