计算复杂度 - 版本历史

薄荷：/* 在算法设计中的应用 */

2021-09-23T11:39:19Z

在算法设计中的应用

唐糖糖：/* 编者推荐 */

2021-09-23T09:03:21Z

编者推荐

唐糖糖：/* 编者推荐 */

2021-09-23T09:02:38Z

编者推荐

唐糖糖：/* 编者推荐 */

2021-09-23T09:02:01Z

编者推荐

唐糖糖：/* 编者推荐 */

2021-09-23T09:01:39Z

编者推荐

唐糖糖：/* 编者推荐 */

2021-09-23T09:01:17Z

编者推荐

唐糖糖：/* 编者推荐 */

2021-09-23T08:54:55Z

编者推荐

2021年9月23日 (四) 08:52 唐糖糖

2021-09-23T08:52:43Z

2021年9月23日 (四) 08:35 唐糖糖

2021-09-23T08:35:15Z

唐糖糖：/* 确定性模型 */

2021-09-23T08:33:54Z

确定性模型

@@ 第128行： / 第128行： @@
-有一个常见的误解，由于'''摩尔定律 Moore's law'''假定了现代计算机功率的'''指数增长 exponential growth'''，对算法复杂度的评估将变得不那么重要。这是错误的，因为这种功率增加同样也会容使得处理较大的输入数据('''大数据 big data''')成为可能。例如，当一个人想要按字母顺序对数百个条目的列表进行排序时，比如一本书的'''参考书目 bibliography'''，任何算法都应该在不到一秒的时间内就能正常工作。另一方面，对于一个包含100万个条目的列表(例如一个大城镇的电话号码) ，需要<math>O(n^2)</math>次比较的基本算法，须进行1万亿次比较运算，即以每秒1000万次的速度进行比较需要大约3个小时。另一方面，'''快速排序 quicksort'''和'''合并排序 merge sort'''只需要<math>n\log_2 n</math>次比较(前者为平均情况复杂度，后者为最坏情况复杂度)。这大约是3000万次比较，以每秒1000万次比较计算，只需要3秒钟。
+有一个常见的误解，由于'''摩尔定律 Moore's law'''假定了现代计算机功率的'''指数增长 exponential growth'''，对算法复杂度的评估将变得不那么重要。这是错误的，因为这种功率增加同样也会容使得处理较大的输入数据（大数据）成为可能。例如，当一个人想要按字母顺序对数百个条目的列表进行排序时，比如一本书的参考书目，任何算法都应该在不到一秒的时间内就能正常工作。另一方面，对于一个包含100万个条目的列表(例如一个大城镇的电话号码) ，需要<math>O(n^2)</math>次比较的基本算法，须进行1万亿次比较运算，即以每秒1000万次的速度进行比较需要大约3个小时。另一方面，快速排序和合并排序 只需要<math>n\log_2 n</math>次比较(前者为平均情况复杂度，后者为最坏情况复杂度)。这大约是3000万次比较，以每秒1000万次比较计算，只需要3秒钟。
 因此，对复杂度的评估允许在编程实现之前就消除许多低效率的算法。这也可用于在不用测试所有变量的情况下调优复杂的算法。通过确定复杂算法中最复杂的步骤，对复杂度的研究还可以将重点放在这些步骤上，从而提高实现的效率。
 ==更多资料==

@@ 第191行： / 第191行： @@
 == 编者推荐 ==
 ===集智文章推荐===
 '''[https://swarma.org/?p=10487 找到你混乱生活中的秩序——Kolmogorov复杂度]'''
@@ 第200行： / 第198行： @@
 '''[https://swarma.org/?p=4240 量子计算时代的机器学习]'''
 现在机器学习这么火，大家自然想知道以后20、30年人工智能会往哪个方向发展。而正如我们之前说到的，人工智能的发展离不开计算力按摩尔定律地提升，当我们把芯片做得越来越小，晶体管的尺寸越来越接近单个原子的大小，这个时候量子效应就会出现，干扰器件的正常工作，比如以前晶体管可以通过电流是否通过来表示开和关，当有量子效应后，原本不能流过的电子现在有一定的概率”隧穿“（tunnel）过去，导致晶体管没法继续工作了。所以摩尔定律会不再成立了，那我们怎么办？
 一个方案就是量子计算芯片，储存的对象不再是bit，而是qubit，外部设备把命令发送给芯片，芯片以量子的方式处理完信息后再把结果传出去。由于量子效应需要极低的温度（毫K量级），我们现在看到的房间那么大的量子计算机其实绝大部分是冷却装置，真正的量子的部分只有最中心的那块芯片。
@@ 第208行： / 第206行： @@
 '''[https://swarma.org/?p=16306 如何把量子计算机调教成终极随机数生成器？]'''
 随机数在计算机和密码学等领域有广泛的应用，目前已经有了许多生成随机数的方法。但事实上，任何基于经典力学的过程所产生的随机数，本质上都不是真随机的。而量子世界特有性质使得可以从中产生可以验证的纯随机 (pure random) 数。本文将介绍两个把量子计算机变成随机数制造工厂的技术。
@@ 第214行： / 第213行： @@
 '''[https://swarma.org/?p=28181 张量网络解码器助力量子纠错 | 复杂性科学顶刊精选6篇]'''
 年7月19日-7月25日来自Complexity Express的复杂性科学论文精选。

@@ 第199行： / 第199行： @@
-[https://swarma.org/?p=4240 量子计算时代的机器学习]
+'''[https://swarma.org/?p=4240 量子计算时代的机器学习]'''
 现在机器学习这么火，大家自然想知道以后20、30年人工智能会往哪个方向发展。而正如我们之前说到的，人工智能的发展离不开计算力按摩尔定律地提升，当我们把芯片做得越来越小，晶体管的尺寸越来越接近单个原子的大小，这个时候量子效应就会出现，干扰器件的正常工作，比如以前晶体管可以通过电流是否通过来表示开和关，当有量子效应后，原本不能流过的电子现在有一定的概率”隧穿“（tunnel）过去，导致晶体管没法继续工作了。所以摩尔定律会不再成立了，那我们怎么办？
@@ 第207行： / 第207行： @@
-[https://swarma.org/?p=16306 如何把量子计算机调教成终极随机数生成器？]
+'''[https://swarma.org/?p=16306 如何把量子计算机调教成终极随机数生成器？]'''
 随机数在计算机和密码学等领域有广泛的应用，目前已经有了许多生成随机数的方法。但事实上，任何基于经典力学的过程所产生的随机数，本质上都不是真随机的。而量子世界特有性质使得可以从中产生可以验证的纯随机 (pure random) 数。本文将介绍两个把量子计算机变成随机数制造工厂的技术。
-[https://swarma.org/?p=28181 张量网络解码器助力量子纠错 | 复杂性科学顶刊精选6篇]
+'''[https://swarma.org/?p=28181 张量网络解码器助力量子纠错 | 复杂性科学顶刊精选6篇]'''
 年7月19日-7月25日来自Complexity Express的复杂性科学论文精选。

@@ 第194行： / 第194行： @@
 [[file:swarma5-1562061006.gif  |thumb|right|280px|我们的目标是获得一个完全随机且滔滔不绝的 01 数据流]]
-[https://swarma.org/?p=10487 找到你混乱生活中的秩序——Kolmogorov复杂度]
+'''[https://swarma.org/?p=10487 找到你混乱生活中的秩序——Kolmogorov复杂度]'''
 如何判断一段话信息量是大是小？在香农那里，可以用“克服了多少不确定性”来描述。而在柯尔莫哥洛夫那里，要看“用多长的代码能生成这句话”。

@@ 第191行： / 第191行： @@
 == 编者推荐 ==
 ===集智文章推荐===
 [https://swarma.org/?p=10487 找到你混乱生活中的秩序——Kolmogorov复杂度]
@@ 第198行： / 第200行： @@
 [https://swarma.org/?p=4240 量子计算时代的机器学习]
 现在机器学习这么火，大家自然想知道以后20、30年人工智能会往哪个方向发展。而正如我们之前说到的，人工智能的发展离不开计算力按摩尔定律地提升，当我们把芯片做得越来越小，晶体管的尺寸越来越接近单个原子的大小，这个时候量子效应就会出现，干扰器件的正常工作，比如以前晶体管可以通过电流是否通过来表示开和关，当有量子效应后，原本不能流过的电子现在有一定的概率”隧穿“（tunnel）过去，导致晶体管没法继续工作了。所以摩尔定律会不再成立了，那我们怎么办？
@@ 第207行： / 第208行： @@
 [https://swarma.org/?p=16306 如何把量子计算机调教成终极随机数生成器？]
 随机数在计算机和密码学等领域有广泛的应用，目前已经有了许多生成随机数的方法。但事实上，任何基于经典力学的过程所产生的随机数，本质上都不是真随机的。而量子世界特有性质使得可以从中产生可以验证的纯随机 (pure random) 数。本文将介绍两个把量子计算机变成随机数制造工厂的技术。

←上一版本		2021年9月23日 (四) 08:54的版本
第196行：		第196行：

	[https://swarma.org/?p=4240 量子计算时代的机器学习]		[https://swarma.org/?p=4240 量子计算时代的机器学习]
−	[[file: swarma8-1534231992.jpeg \|thumb\|right~~\|280px~~]]	+	[[file: swarma8-1534231992.jpeg \|thumb\|280px\|right]]

←上一版本		2021年9月23日 (四) 08:52的版本
第194行：		第194行：
	====[https://swarma.org/?p=10487 找到你混乱生活中的秩序——Kolmogorov复杂度]====		====[https://swarma.org/?p=10487 找到你混乱生活中的秩序——Kolmogorov复杂度]====
	如何判断一段话信息量是大是小？在香农那里，可以用“克服了多少不确定性”来描述。而在柯尔莫哥洛夫那里，要看“用多长的代码能生成这句话”。		如何判断一段话信息量是大是小？在香农那里，可以用“克服了多少不确定性”来描述。而在柯尔莫哥洛夫那里，要看“用多长的代码能生成这句话”。
		+
		+	[https://swarma.org/?p=4240 量子计算时代的机器学习]
		+	[[file: swarma8-1534231992.jpeg \|thumb\|right\|280px]]
		+
		+
		+	[https://swarma.org/?p=16306 如何把量子计算机调教成终极随机数生成器？]
		+	[[file:swarma5-1562061006.gif \|thumb\|right\|280px\|我们的目标是获得一个完全随机且滔滔不绝的 01 数据流]]
		+
		+	[https://swarma.org/?p=28181 张量网络解码器助力量子纠错 \| 复杂性科学顶刊精选6篇]
		+
		+
		+
		+
		+
		+
		+
		+
		+

←上一版本		2021年9月23日 (四) 08:35的版本
第3行：		第3行：
	\|description=在'''计算机科学 computer science'''中，一个'''算法 algorithm'''的'''计算复杂度'''或简单的'''复杂度'''就是运行这个算法所需要的资源量，特别是'''时间'''（CPU占用时间）和'''空间'''（内存占用空间）需求。		\|description=在'''计算机科学 computer science'''中，一个'''算法 algorithm'''的'''计算复杂度'''或简单的'''复杂度'''就是运行这个算法所需要的资源量，特别是'''时间'''（CPU占用时间）和'''空间'''（内存占用空间）需求。
	}}		}}
−
−	~~{{Short description\|amount of resources (usually time and/or memory) to perform an algorithm}}~~

@@ 第70行： / 第70行： @@
 ===确定性模型===
-一个'''确定性模型 deterministic model '''的计算是一种机器的后续状态和要执行的操作完全由前面的状态决定的计算模型。历史上，最早的确定性模型是'''[[递归]]函数 recursive functions'''、 '''lambda 演算 lambda calculus'''和'''[[图灵机]] Turing machines'''。'''随机存取机器 Random access machine '''(也称 RAM-machines)的模型也被广泛使用，更接近真实的'''计算机 computer'''。
+一个'''确定性模型 deterministic model '''的计算是一种机器的后续状态和要执行的操作完全由前面的状态决定的计算模型。历史上，最早的确定性模型是'''[[递归]]函数 recursive functions'''、 '''lambda演算 lambda calculus'''和'''[[图灵机]] Turing machines'''。'''随机存取机器 Random access machine '''(也称 RAM-machines)的模型也被广泛使用，更接近真实的'''计算机 computer'''。
 当计算模型没有被指定时，通常假设它是一个'''多带图灵机 multitape Turing machine'''。对于大多数算法，在多带图灵机上的时间复杂度与在RAM-machines上的相同，尽管可能需要注意如何将数据存储在内存中，以确保这种等价性.
 ===非确定性计算===