[quote]to justforfun626:

I don't think you are right, because of Hash. You don't know the hash function and how Ruby store all the numbers in the memory. It is inexact to say "it is O(n)".

I don't think high level language is proper for algorithm analysis, although I like them very much.[/quote]

To ggggqqqqihc
Haha, have you tried it, tested it???

[size=3][b]What you think or think not does not matter at all, the important thing is what is the fact!!!

[color=red]If you don't know what you are talking about, please stop talking and start to learn!!![/size]

Thanks![/color][/b]

fun大概想说明这个意思:

[code=c]

int fibonacci(int n)
{
    static int fib[MAX] = {0}; // 假设int不会溢出
    static int max_n = 0;
    assert(n < MAX);
    while(n > max_n && max_n < MAX)
    {
        max_n++;
        if(max_n <= 2) fib[max_n] = 1;
        else fib[max_n] = fib[max_n-1] + fib[max_n-2];
    }
    return fib[min(n, MAX-1)];
}

[/code]

这个时间复杂度应该是O(1)，空间复杂度是无穷大。（理论上来说）

用空间换时间。一般来说，规模有上限的前提下可以这么做。

不过在规模没有上限的前提下，这个方法不可靠，因为不可能有无穷大的空间供你支配。

[quote]fun大概想说明这个意思:

[code=c]

int fibonacci(int n)
{
    static int fib[MAX] = {0}; // 假设int不会溢出
    static int max_n = 0;
    assert(n < MAX);
    while(n > max_n && max_n < MAX)
    {
        max_n++;
        if(max_n <= 2) fib[max_n] = 1;
        else fib[max_n] = fib[max_n-1] + fib[max_n-2];
    }
    return fib[min(n, MAX-1)];
}

[/code]

这个时间复杂度应该是O(1)，空间复杂度是无穷大。（理论上来说）

用空间换时间。一般来说，规模有上限的前提下可以这么做。

不过在规模没有上限的前提下，这个方法不可靠，因为不可能有无穷大的空间供你支配。
[/quote]


这不是输出数列吗？不用数组，两个变量相互做加法、输出不是更好？

[img]http://urbandecals.com/shutup.jpg[/img]

[color=red][b][size=3]Can you all stop misinterpreting what I mean, please???

If you don't know what you are talking about, please stop talking and start to learn!!!
[/size][/b][/color]

Thanks!

fun已经说了他的程序是O(n)的,但是算了n=10000之后,再算n<10000的数,就几乎不要时间,因为前面的数都存在'Hash'表里面,你只需要读出来,如果你还想算n>10000的斐数,他有一个更好的程序在他的个人主页里,请去参考一下.
而后面一位朋友是说,他认为Ruby是高级语言,你不知道那个Hash是如何实现的,所以不能说是O(n)
我也不太了解Ruby，所以我不敢评论，但是O(n)的O(logn)是相差很多的，算斐数算是很轻松的事情对于很多C/C++大数库来说，不要说n=10000，就算是阶乘也算不上什么鸡毛蒜皮的事，如果O(n)的算法算10,000要1s，那算10,000,000至少要大1000倍，还不考虑你的大数基本运算的时间开销，而O(logn)的算法可能只需要2s，只是一个感性比较。

Test my code is very simple.

1) Download ruby, install it, make sure downloading the correct one for your OS
2) Append your ruby_dir/bin to your path/PATH
3) Copy and save my code as fib.rb or whatever.rb
4) Open a cmd/console window or unix terminal in the directory contain the file
5) type [b]ruby fib.rb[/b]
6) You got the result

You don't need to understand ruby syntax to test my code.

to justforfun626:

虽然我没有用Ruby做过项目，但你的代码我想我还是能明白的。
虽然hash table是一个近似于O(1)的操作，整体代码的复杂度也的确是O(n)，但高阶的语言掩盖了算法的复杂度。假如你用一种tree map数据结构，那复杂度就会接近O(nlogn)，但体现在代码中的复杂度看起来还是O(n)——如果你不知道内部采用的数据结构的话。

好比有些人写一个将小写字母变成大写的代码：
[code=c]
for (int i=0;i<strlen(s);++i){
  s[i]=toupper(s[i]);
}
[/code]
看起来是O(n)，实际上是O(n^2)（因为C语言的strlen复杂度是O(n)）。

当然你的代码是很快的，就算是算10000000项也很快，但算法分析不是测量运行时间。

[quote]fun已经说了他的程序是O(n)的,但是算了n=10000之后,再算n<10000的数,就几乎不要时间,因为前面的数都存在'Hash'表里面,你只需要读出来,如果你还想算n>10000的斐数,他有一个更好的程序在他的个人主页里,请去参考一下.
而后面一位朋友是说,他认为Ruby是高级语言,你不知道那个Hash是如何实现的,所以不能说是O(n)
我也不太了解Ruby，所以我不敢评论，但是O(n)的O(logn)是相差很多的，算斐数算是很轻松的事情对于很多C/C++大数库来说，不要说n=10000，就算是阶乘也算不上什么鸡毛蒜皮的事，如果O(n)的算法算10,000要1s，那算10,000,000至少要大1000倍，还不考虑你的大数基本运算的时间开销，而O(logn)的算法可能只需要2s，只是一个感性比较。[/quote]


他的改进算法没看很明白，但是所谓改进，无非就是不再重复计算已经计算过的数，或者尽量减少重复计算。时间换空间的本质没有改变，空间复杂度O(max(n)/200)和O(max(n))都将趋向无穷大，没有本质的区别。

F数列的矩阵算法看了一下，大概就是让x=(1,0)重复乘以一个2*2的矩阵因子A：
1 1
1 0
最后(fn, fn-1) = x * A^n

而A的n次幂可以用反复平方法获得O(logn)的低复杂度， x * A^n实际上就是取A^n矩阵的第一行。

To ggggqqqqihc
Haha, have you tried it, tested it???

[size=3][b]What you think or think not does not matter at all, the important thing is what is the fact!!!

[color=red]If you don't know what you are talking about, please stop talking and start to learn!!![/size]

Thanks![/color][/b]

[code=c]for (int i=0;i<strlen(s);++i){
  s[i]=toupper(s[i]);
}[/code]

Nobody will write such stupid code, except ...
[img]http://www.starstore.com/acatalog/Shrek_2_Donkey_L_poster.jpg[/img]