一家之言 - Programming版

本页内容为未名空间相应帖子的节选和存档，一周内的贴子最多显示50字，超过一周显示500字访问原贴

相关主题
● 王垠：图灵的光环 (转载)	● 请问不用开方怎么算N个复数的模之和？
● [bssd]计算机科学的自然律	● 问一个算法题，可能比较老了，KNN
● Machin learning is hype	● Mathematica下面做function fit
● c++ define 一问	● 请问如何把初始化一个const 的vector (or array) in a class?
● 一个数据结构中的数学求和问题求教 (转载)	● C++一问
● 一个哈希表问题	● 把一个function pointer作为参数传入一个function的语法是什么？
● 简单问题的有限差分	● [合集] 常数指针的问题
● cost time of shift operation?	● C语言算10的X次方怎么算才快？

相关话题的讨论汇总
话题: 计算话题: 不同话题: 渐进话题: 分析话题: turing

进入Programming版参与讨论

(共1页)

c*******v
发帖数: 2599

渐进分析里的多项式计算次数，牛顿时代就有了。
我压根不记得现在这套计算理论的术语符号。我自用的都是渐进分析那套。
我书架上就有一渐进分析的书。但是这个，以及recursion function提及的多项式
计算啥的和图灵的概念之间差一个universal turing machine。
图灵提出了Universal Turing Machine，证明了不同计算模型的，不同机器上的计算，
不同语言，不同。。。的计算的overhead都是常数。常数属于多项式.
这就使得计算复杂度P的定义，脱离了不同的计算模型，以及不同计算模型的具体不同
机器。这就把计算复杂度上升到了理论高度，成为脱离于在时间和世界内发生的具体计
算过程之外的东西，也就是说，上升到了理论高度。这叫开宗立派。
其他的结果，哪怕中国古代的渐进分析计算次数分析结果，在逻辑上都是Universal
Turing Machine之后的。
算盘是图灵完备的。是没有折扣的计算机。
你不能拿本古代的算盘指法P次数分析结果，就说计算复杂度是中国古人发明的。
前者乃是具体的一个问题。后者是一个理论.

(共1页)

进入Programming版参与讨论

相关主题
● 有难度的面试题	● 一个数据结构中的数学求和问题求教 (转载)
● 超简单一道题	● 一个哈希表问题
● 弱弱的问个关于C++的问题：如何创建一个存放常数数组的文件，	● 简单问题的有限差分
● matlab问题	● cost time of shift operation?
● 王垠：图灵的光环 (转载)	● 请问不用开方怎么算N个复数的模之和？
● [bssd]计算机科学的自然律	● 问一个算法题，可能比较老了，KNN
● Machin learning is hype	● Mathematica下面做function fit
● c++ define 一问	● 请问如何把初始化一个const 的vector (or array) in a class?

相关话题的讨论汇总
话题: 计算话题: 不同话题: 渐进话题: 分析话题: turing

#	版面	帖数(主题数)
-	全站	4871 (796)
1	Military	3777 (569)
2	Stock	341 (51)
3	Joke	117 (17)
4	History	116 (3)
5	Automobile	100 (9)
6	USANews	55 (9)
7	Midlife	45 (1)
8	Headline	41 (41)
9	Dreamer	33 (13)
10	FleaMarket	32 (20)
11	Living	30 (7)

boards

未名新帖统计// 7月16日

历史上的今天