讨论一个算法

emacsnw

空间O(n)的话可以维持一个hash table啊，顺序scan这个数组，把出现过的数字加入这个hash表。当碰到已经加过的数字就返回，时间O(n)。

flw

原帖由 emacsnw 于 2007-3-20 15:49 发表
空间O(n)的话可以维持一个hash table啊，顺序scan这个数组，把出现过的数字加入这个hash表。当碰到已经加过的数字就返回，时间O(n)。

其实还可以 O(1)，插入时 scan 这个数组，把重复的那一对放到数组的最前面。取的时候只需要判断数组开头的两个数是否一样就行了。一样就返回，不一样就说明全都不重复。

lenovo

原帖由 flw 于 2007-3-20 15:56 发表

其实还可以 O(1)，插入时 scan 这个数组，把重复的那一对放到数组的最前面。取的时候只需要判断数组开头的两个数是否一样就行了。一样就返回，不一样就说明全都不重复。

没看太懂，能不能说得明白些？

flw

原帖由 lenovo 于 2007-3-20 16:32 发表

没看太懂，能不能说得明白些？

简而言之，就是把想要的数据提前准备好，然后等用的时候直接拿来用，就是 O(1) 了。
linux 2.6 著名的 O(1) 调度算法就是这么标榜自己的。
另外，几乎所有的老板做事效率都是 O(1) 的，因为 O(n^3) 那是员工的复杂度。

lenovo

原帖由 flw 于 2007-3-20 16:34 发表

简而言之，就是把想要的数据提前准备好，然后等用的时候直接拿来用，就是 O(1) 了。
linux 2.6 著名的 O(1) 调度算法就是这么标榜自己的。
另外，几乎所有的老板做事效率都是 O(1) 的，因为 O(n^3) 那是员工的 ...

这个意思呀，那这个“想要的数据提前准备好”不算在内么？

flw

原帖由 lenovo 于 2007-3-20 16:38 发表

这个意思呀，那这个“想要的数据提前准备好”不算在内么？

对。因为那个不占用检索时间。只占用插入时间。

lenovo

原帖由 flw 于 2007-3-20 16:41 发表

对。因为那个不占用检索时间。只占用插入时间。

这个，有点晕。
这样吧，随便给一个数组
int a[] = {1， 3， 5， 9， 5， 10， 11， 30， 2， 13}
flw你能给我一个具体的O（1）算法么？
伪码也行，我脑袋糊了。

flw

原帖由 lenovo 于 2007-3-20 16:46 发表

这个，有点晕。
这样吧，随便给一个数组
int a[] = {1， 3， 5， 9， 5， 10， 11， 30， 2， 13}
flw你能给我一个具体的O（1）算法么？
伪码也行，我脑袋糊了。

你没事干随便给干什么？
你既然要给，就给整齐点不行吗？

blackuhlan

flw的说法等价于如果给我一个操作系统的代码,我也可以写时间复杂度为O(1)的操作系统,调用它就行了.
这样有意义吗?
另外hash table不用耗时间的说?还O(n),hash table你每次加入一个数据就要进行一次排序,不要时间?
讨论算法的时候用成品还要说成品是不计算成本的,脑壳有包!

flw

原帖由 blackuhlan 于 2007-3-20 16:53 发表
flw的说法等价于如果给我一个操作系统的代码,我也可以写时间复杂度为O(1)的操作系统,调用它就行了.
这样有意义吗?
另外hash table不用耗时间的说?还O(n),hash table你每次加入一个数据就要进行一次排序,不要时间 ...

恭喜你！
等着被扣分吧。