{技术}{可计算理论}有没有和自然时间相关的常数O(1)算法?

428 views
Skip to first unread message

est

unread,
Jun 25, 2009, 11:10:38 AM6/25/09
to pon...@googlegroups.com
小弟不是CS专业出生,对Computability theory也不是很熟悉,但是有一天我想到了一个很有趣的问题

假如我们1个problem,1个单位计算能力能够解决,2个同类problem能用2个单位计算力能够解决,3个problem用3个计算能力。那么我们说这个算法是O(n)线性增长的

如果另一个problem,1个单位计算能力能够解决,2个问题必须用4个,那么我们说这个算法是  O(n^2) 的

如果说道上面这些我都还没有犯严重的根本性错误的话,那么我有如下问题:

有没有可能存在这样一个problem,假如我要花24个小时才能解决,2个同类的problem,我们仍然需要24小时;也就是在自然时间尺度上是O(1) 的

1. 有没有可能存在这种problem?
2. 假如存在这种problem,有没有可能存在 O(n) 或者 O(n^2) 自然时间增长率的类似problem?

对于这种problem存在的可能性,有一个伪例子,就是sleep函数。假如我们一个函数是 sleep(24 hours) 那么无论怎么都必须呆够24小时才能得到结果。

当然在一台具体PC上计算这个问题,我们可以通过修改CPU时钟频率来hack掉这个函数。那么我们可否设计一种逻辑电路,来达到和自然界时间流逝速度线性一致的算法?

Wu Yin

unread,
Jun 25, 2009, 12:05:25 PM6/25/09
to pon...@googlegroups.com
看不懂你所谓的“X个problem”是什么意思。
比如说一个问题你需要1单位时间解决,那么解决两个问题,所花的时间当然是1*2,何来4个之说?
所谓的复杂性里的n并不是指问题的个数,而是指问题的规模。比如说,某个问题是对很多数字进行运算,这里面数字的个数n是问题的规模。问题还是这么一个问题,它的规模不同,需要的时间也不同。所谓的复杂度,并不是问题的个数变多了。

2009/6/25 est <electr...@gmail.com>



--
滚滚长江东逝水,浪花淘尽英雄。
是非成败转头空。
青山依旧在,几度夕阳红。
白发渔樵江渚上,惯看秋月春风。
一壶浊酒喜相逢。
古今多少事,都付笑谈中。

Wu Yin

unread,
Jun 25, 2009, 12:10:52 PM6/25/09
to pon...@googlegroups.com
还有,sleep和你所说的时间复杂度不是一个问题。
所谓时间复杂度,名为时间,但考虑的其实并不是实际的运行时间。它考察的只是瓶颈运算(加法,减法,赋值等等)的次数。当然,运算的次数越多,所需的时间自然也就越多,所以才有了什么“时间复杂度”一类的称呼。
所以拿sleep举例分析时间复杂度根本没有任何的价值,因为这两个根本就是不同的问题。

2009/6/26 Wu Yin <wyw...@gmail.com>

Doyle

unread,
Jun 25, 2009, 8:31:20 PM6/25/09
to pon...@googlegroups.com
同意

2009/6/26 Wu Yin <wyw...@gmail.com>:

--

Yogi Berra - "I never said most of the things I said." -
http://www.brainyquote.com/quotes/authors/y/yogi_berra.html

Rockins Chen

unread,
Jun 25, 2009, 8:39:57 PM6/25/09
to pon...@googlegroups.com
通常来讲,应该这样来理解O(1):一个规模为n的问题,解决它的时间是一个常数时间t。对于你说的这种情况,是不是可以这样理解:对于一个规模为n的问题,求解需要24小时,对于一个规模为2n的问题,求解仍然需要24小时。很多简单问题都是O(1)复杂度的,比如:从一个数组中取出首元素,无论数组的大小是100还是1000,这个操作都是常数时间的。

BRs
Rockins Chen

2009/6/25 est <electr...@gmail.com>



--
BRs,
Rockins Chen
~~~~~~~~~~~~~~~~~~~~~~~~~~~~
UESTC, Chengdu, Sichuan, China
http://rockins.cn/
ybc...@gmail.com

Daniel Lv

unread,
Jun 25, 2009, 8:50:28 PM6/25/09
to pon...@googlegroups.com
我认为我们之所以要分析算法并采用Big-O来标记算法效率的目的,是用于比较以及针对具体问题作算法选型的!
我不怀疑你说的这种情况(问题规模扩大一倍,复杂度仍然是O(n))是否存在,但是如果候选算法都有一样的效率,那么可以视为他们是一样的

2009/6/26 Rockins Chen <ybc...@gmail.com>

51isoft

unread,
Jun 25, 2009, 11:16:47 AM6/25/09
to pon...@googlegroups.com
我试着回答下,我第一次发帖,大虾们见笑~

1、有可能,当你的每一步之间没有逻辑关系时,我们可以使用并行计算完成(CUDA一类)

2、一般说O(N^2)的算法每一步肯定是有逻辑关系的,所以不能简单的说降为O(N)。

2009/6/25 est <electr...@gmail.com>

DaNmarner

unread,
Jun 25, 2009, 4:59:48 PM6/25/09
to TopLanguage
回复最后一句: 量子算机可以很轻易的实现

qing yin

unread,
Jun 25, 2009, 10:59:11 PM6/25/09
to pon...@googlegroups.com
如果一个算法解决一个问题的复杂度是O(n),就算这个问题规模扩大了,但原算法依然有效的情况下,复杂度还是O(n)
lz所说的东西,和你最算法复杂度的理解,有点乱

凭借我对你sleep所举例子的理解,你所谓的自然时间复杂度,和算法复杂度,压根就不是一回事

wuyin说的东西,建议理解下,然后多看看类似算法导论上面关于时间复杂度的介绍吧


2009/6/26 Daniel Lv <lgn...@gmail.com>

Wu Yin

unread,
Jun 26, 2009, 2:10:42 AM6/26/09
to pon...@googlegroups.com
时间复杂度和实际运行时间是两码事。如果说二者有什么关系的话,时间复杂度是实际运行时间对问题规模的函数。也就是说,时间复杂度并不是一个数,而是一个函数。Big-O的意义也并不是将某个特定的规模n代入之后相等,而是表示在n趋于正无穷大之时,该算法所需要的运行时间(注意,n趋于无穷大时,运行时间也应该趋于无穷大)和Big-O内部的函数值 是同一阶的无穷大(无穷大同阶的概念参见数学分析)。
笼统点说,时间复杂度并不是表示实际运行时间,而是表示 在问题越来越难的情况下(绝大多数的问题,规模越大,问题越难解决,对吧),解决问题所需要的时间的 变化趋势。
所以,在STL 的sort里面,在问题缩小到一定规模之后,仍然会采用时间复杂度比快排大的插入排序,因为在问题规模变小的时候,所谓的Big-O已经失去它的意义了。

2009/6/26 Daniel Lv <lgn...@gmail.com>

tangl_99

unread,
Jun 26, 2009, 5:55:27 AM6/26/09
to TopLanguage
你自称不是CS专业出生,对计算理论也不熟悉,那么你就应该先熟悉一下计算理论了来再来提问。因为当你熟悉之后,你自己应该就可以回答这个问题。没有必
要跑到这里来寻找答案。

张沈鹏

unread,
Jun 26, 2009, 12:06:21 PM6/26/09
to pon...@googlegroups.com
....
回去看书

chaoyan ma

unread,
Jun 26, 2009, 1:04:28 PM6/26/09
to pon...@googlegroups.com
并行计算吗~

在 09-6-27,张沈鹏<zsp...@gmail.com> 写道:
> ....
> 回去看书
>

罗永明

unread,
Jun 26, 2009, 8:18:57 PM6/26/09
to TopLanguage
你对BigO的理解是错误的

On 6月25日, 下午11时10分, est <electronix...@gmail.com> wrote:
> 小弟不是CS专业出生,对Computability theory也不是很熟悉,但是有一天我想到了一个很有趣的问题

> 假如我们1个problem,1个单位计算能力能够解决,2个同类problem能用2个单位计算力能够解决,3个problem用3个计算能力。那么我们说这-个算法是O(n)线性增长的


>
> 如果另一个problem,1个单位计算能力能够解决,2个问题必须用4个,那么我们说这个算法是 O(n^2) 的
>
> 如果说道上面这些我都还没有犯严重的根本性错误的话,那么我有如下问题:
>
> 有没有可能存在这样一个problem,假如我要花24个小时才能解决,2个同类的problem,我们仍然需要24小时;也就是在自然时间尺度上是O(1) 的
>
> 1. 有没有可能存在这种problem?
> 2. 假如存在这种problem,有没有可能存在 O(n) 或者 O(n^2) 自然时间增长率的类似problem?
>
> 对于这种problem存在的可能性,有一个伪例子,就是sleep函数。假如我们一个函数是 sleep(24 hours)
> 那么无论怎么都必须呆够24小时才能得到结果。
>

> 当然在一台具体PC上计算这个问题,我们可以通过修改CPU时钟频率来hack掉这个函数。那么我们可否设计一种逻辑电路,来达到和自然界时间流逝速度线性一致-的算法?

est

unread,
Jun 27, 2009, 2:50:27 AM6/27/09
to pon...@googlegroups.com
可否具体说说量子计算是什么情况?其实我就是想问这个问题,只是错误的用了复杂度来引入这个话题。。。。失误失误让各位见笑了。。。。。。。

2009/6/26 DaNmarner <danm...@gmail.com>

est

unread,
Jun 27, 2009, 3:29:50 AM6/27/09
to pon...@googlegroups.com
非常抱歉浪费了大牛们的时间,但是希望大牛在批评我的错误同时,也能看到我问题本身不是对BigO提问的。我非常傻逼的用BigO来说明我的问题,其实我的问题的本身就是说有没有一个算法是time unscalable的。其实发信到Toplang之前我已经意识到这个(愚蠢)的想法和普朗克常数h有关了,但是从量子力学的角度说明我也不大会,所以还是通过BigO这个方式来描述了我的问题。。。。。我也预料到TopLang的各位可能会把话题集中在BigO的错误描述上,所以在开头就说明了我对BigO的理解可能是错误的。

总之希望大家在批评我的同时也能讨论下我的想法。。。。同时我会加倍努力学习计算理论的。。。。

2009/6/26 tangl_99 <tan...@gmail.com>

张沈鹏

unread,
Jun 27, 2009, 5:55:14 AM6/27/09
to pon...@googlegroups.com
http://chenjun21st.blog.163.com/blog/static/3988002007112201670/

接下来我们看看量子计算机如何对这些态进行运算。假设现在我们想求一个函数f(n),(n=0~7)的值,采用经典计算的办法至少需要下面的步骤:

存储器清零→赋值运算→保存结果→再赋值运算→再保存结果……

对每一个n都必须经过存储器的赋值和函数f(n)的运算等步骤,而且至少需要8个存储器来保存结果。如果是用量子计算机来做这个题目则在原理上要简洁的多,只需用一个量子存储器,把各q-bit制备到(
|0〉+ |1〉) / (√2)态上就一次性完成了对8个数的赋值,此时存储器成为态
|φ〉,然后对其进行相应的幺正变换以完成函数f(n)的功能,变换后的存储器内就保存了所需的8个结果。这种能同时对多个态进行操纵,所谓“量子并行计算”的性质正是量子计算机巨大威力的奥秘所在。

2009/6/27 est <electr...@gmail.com>:

--
弓长
孝文


http://zsp.javaeye.com/

qing yin

unread,
Jun 26, 2009, 4:30:55 AM6/26/09
to pon...@googlegroups.com
re WuYin

2009/6/26 Wu Yin <wyw...@gmail.com>

Yingjie XU

unread,
Jun 28, 2009, 4:16:51 AM6/28/09
to pon...@googlegroups.com
你能不能把你的问题说清楚,就算是量子算法,跟普朗克常数也没什么关系。。。

2009/6/27 est <electr...@gmail.com>



--
Yingjie XU
Département d'informatique
École Normale Supérieure
45 rue d'Ulm
F-75230 Paris Cedex 05

"If you received this communication by mistake,
please don't forward it to anyone else (it may contain
confidential or privileged information), please erase
all copies of it, including all attachments, and please
let the sender know it went to the wrong person.
Thanks."

DaNmarner

unread,
Jul 2, 2009, 9:23:53 PM7/2/09
to TopLanguage
理论上,量子计算的信号转换时间取决于分子状态变化的频率,而这个频率本身就是用自然时间来衡量的。这决定了特定计算机指令的运行速度也较容易用自然时
间衡量。推而广之,现在理论上的O(1)也就有了一个自然时间的基础。

试想,有多少物理学论著里研究过类似"预测电流在电路里的传播速度"这样的问题?得到这个问题的答案不是不可能,而是没有意义,因为电流电阻电压这些概
念是电磁学太初通过简单粗糙的实验生造出来的,它们产生的时候能够用来观察相关现象的时间特征的技术连在娘胎里都找不到,所以用他们把O(1)和自然时
间联系起来是水土不服的。

量子计算在这个问题上的优越性在于分子态变化(比率)这一现象比电子计算机所基于的电现象更基础,更有可重复性和可预测性。前者处于物理学发展的下游
(量子理论:我站在巨人的头上啊),时间是其理论中最常见的基本量。

当然这都是科学YY,现实里量子计算机能发展成什么样还要看我们的基础科学会有什么重大突破(不禁想起了三体,冷阿)。

On Jun 25, 10:10 am, est <electronix...@gmail.com> wrote:

est

unread,
Feb 1, 2010, 5:05:18 AM2/1/10
to pon...@googlegroups.com
顶个老贴,今天看到关于blowfish的一段介绍

> bcrypt can keep up with Moore’s law. As computers get faster you can increase the work factor and the hash will get slower.

和我期望的东西比较类似,强度和摩尔定律一起增长的加密算法。不知道有没有大牛具体分析一下这其中的原理和机制?

est

unread,
Apr 18, 2018, 3:07:40 AM4/18/18
to TopLanguage]列表
8年之后,终于明白我当时想的就是 proof of work 了。。。

ablozhou

unread,
Apr 18, 2018, 3:16:59 AM4/18/18
to pon...@googlegroups.com
牛,早买比特币那早就发财兼明白了。



--

---
您收到此邮件是因为您订阅了Google网上论坛上的“TopLanguage”群组。
要退订此群组并停止接收此群组的电子邮件,请发送电子邮件到pongba+un...@googlegroups.com
要查看更多选项,请访问https://groups.google.com/d/optout
Reply all
Reply to author
Forward
0 new messages