算法分析 - 版本历史

薄荷：/* 参考文献 */

2021-09-23T13:51:52Z

参考文献

薄荷：/* 相关文章= */

2021-09-23T13:51:38Z

薄荷：/* 编者推荐 */

2021-09-23T13:51:24Z

编者推荐

2021年9月23日 (四) 13:37 薄荷

2021-09-23T13:37:24Z

薄荷：/* 参考文献 */

2021-09-23T13:27:09Z

参考文献

薄荷：/* 参考文献 */

2021-09-23T13:26:59Z

参考文献

薄荷：/* 经验增长规律 */

2021-09-23T13:25:57Z

经验增长规律

薄荷：/* 经验增长规律 Empirical orders of growth */

2021-09-23T13:25:40Z

经验增长规律 Empirical orders of growth

薄荷：/* 经验增长规律 Empirical orders of growth */

2021-09-23T13:23:14Z

经验增长规律 Empirical orders of growth

2021年9月23日 (四) 13:22 薄荷

2021-09-23T13:22:18Z

←上一版本		2021年9月23日 (四) 13:51的版本
第455行：		第455行：

	*{{Cite book \|first=Oded \|last=Goldreich \|title=Computational Complexity: A Conceptual Perspective \|location= \|publisher=Cambridge University Press \|year=2010 \|isbn=978-0-521-88473-0 }}		*{{Cite book \|first=Oded \|last=Goldreich \|title=Computational Complexity: A Conceptual Perspective \|location= \|publisher=Cambridge University Press \|year=2010 \|isbn=978-0-521-88473-0 }}
		+
		+	<br>

	==编者推荐==		==编者推荐==

@@ 第464行： / 第464行： @@
-===相关文章====
+===相关文章===
 * [https://blog.csdn.net/yuxuan20062007/article/details/82095490 算法分析：时间和空间复杂度]
 * [https://www.cnblogs.com/absfree/p/5464779.html 算法分析的正确姿势]

@@ 第457行： / 第457行： @@
 ==编者推荐==
-===集智课程===
+===集智文章===
-====[]====
+====[https://swarma.org/?p=25369 彭兰：算法社会的“囚徒”风险]====

@@ 第3行： / 第3行： @@
 |description=是计算查找算法复杂性的过程——包括算法执行时间、所需存储空间或其他资源的数量
 }}
+[[File:Binary search vs Linear search example svg.svg.png|thumb|为了在给定的有序列表中查找给定的条目，可以使用二进制和线性搜索算法（忽略排序）。对前一种算法和后一种算法的分析表明，对于长度为n的列表，它最多只需要log<sub>2</sub>(''n'')和''n''个检查步骤。在所描述的长度为33的示例列表中，搜索“Morin，Arthur”分别需要5步和28步，使用二进制和线性搜索。]]
-[[File:Binary search vs Linear search example svg.svg|thumb|为了在给定的有序列表中查找给定的条目，可以使用二进制和线性搜索算法（忽略排序）。对前一种算法和后一种算法的分析表明，对于长度为n的列表，它最多只需要log<sub>2</sub>(''n'')和''n''个检查步骤。在所描述的长度为33的示例列表中，搜索“Morin，Arthur”分别需要5步和28步，使用二进制和线性搜索。]]
+[[File:comparison_computational_complexity.svg.png|thumb|在算法分析中常用函数图，表示每个函数的操作数 ''N'' 与输入大小 ''n'' 的对应关系]]
 在计算机科学中，'''算法分析 analysis of algorithms'''是计算查找算法复杂性的过程——包括算法执行时间、所需存储空间或其他资源的数量。通常这是一个确定函数，该函数将一个算法的输入长度与所需的迭代步数（时间复杂度）或使用的存储大小（空间复杂度）相关联。当某个算法其算法复杂性函数的取值很小，或者其函数值大小的增长速度与算法输入大小的相比更加缓慢时，我们认为该算法是有效的。相同长度的不同输入可能导致算法表现出不同的效果，因此对算法运行的最佳、最差和平均情况的描述都可能具有一定的实际意义。但是当没有特殊说明时，算法性能描述函数通常反映的是算法复杂性一种上界，由算法表现最差情况的输入来确定。

@@ 第457行： / 第457行： @@
 *{{Cite book |first=Daniel A. |last=Greene |first2=Donald E. |last2=Knuth |title=Mathematics for the Analysis of Algorithms |edition=Second |location= |publisher=Birkhäuser |year=1982 |isbn=3-7643-3102-X }}
-*{{Cite book |authorlink=Oded Goldreich |first=Oded |last=Goldreich |title=Computational Complexity: A Conceptual Perspective |location= |publisher=Cambridge University Press |year=2010 |isbn=978-0-521-88473-0 }}
+*{{Cite book |first=Oded |last=Goldreich |title=Computational Complexity: A Conceptual Perspective |location= |publisher=Cambridge University Press |year=2010 |isbn=978-0-521-88473-0 }}
 ==编者推荐==

@@ 第449行： / 第449行： @@
 ==参考文献==
 {{reflist}}
-*{{Cite book |first=Thomas H. |last=Cormen |first2=Charles E. |last2=Leiserson |first3=Ronald L. |last3=Rivest |lastauthoramp=yes |authorlink4=Clifford Stein |first4=Clifford |last4=Stein |title=Introduction to Algorithms |edition=Second |publisher=MIT Press and McGraw-Hill |location=Cambridge, MA |year=2001 |isbn=0-262-03293-7 |others=Chapter 1: Foundations |pages=3–122 }}
+*{{Cite book |first=Thomas H. |last=Cormen |first2=Charles E. |last2=Leiserson |first3=Ronald L. |last3=Rivest |lastauthoramp=yes |first4=Clifford |last4=Stein |title=Introduction to Algorithms |edition=Second |publisher=MIT Press and McGraw-Hill |location=Cambridge, MA |year=2001 |isbn=0-262-03293-7 |others=Chapter 1: Foundations |pages=3–122 }}
 *{{Cite book |title=Algorithms in C, Parts 1-4: Fundamentals, Data Structures, Sorting, Searching |edition=3rd |first=Robert |last=Sedgewick |location=Reading, MA |publisher=Addison-Wesley Professional |year=1998 |isbn=978-0-201-31452-6 |url-access=registration |url=https://archive.org/details/algorithmsinc00sedg }}
@@ 第457行： / 第457行： @@
 *{{Cite book |first=Daniel A. |last=Greene |first2=Donald E. |last2=Knuth |title=Mathematics for the Analysis of Algorithms |edition=Second |location= |publisher=Birkhäuser |year=1982 |isbn=3-7643-3102-X }}
-*{{Cite book |authorlink=Oded Goldreich |first=Oded |last=Goldreich |title=Computational Complexity: A Conceptual Perspective |location= |publisher=[[Cambridge University Press]] |year=2010 |isbn=978-0-521-88473-0 }}
+*{{Cite book |authorlink=Oded Goldreich |first=Oded |last=Goldreich |title=Computational Complexity: A Conceptual Perspective |location= |publisher=Cambridge University Press |year=2010 |isbn=978-0-521-88473-0 }}
 ==编者推荐==

←上一版本		2021年9月23日 (四) 13:25的版本
第286行：		第286行：

	可以清楚地看到，第一个算法展示了一个线性增长的序列，这确实遵循幂规则。第二个经验值正在迅速递减，这表明它遵循了另一条增长规律，而且无论如何，从经验上看，其当下的增长（及其进一步的增长）远低于第一个。		可以清楚地看到，第一个算法展示了一个线性增长的序列，这确实遵循幂规则。第二个经验值正在迅速递减，这表明它遵循了另一条增长规律，而且无论如何，从经验上看，其当下的增长（及其进一步的增长）远低于第一个。
		+
		+	<br>

	=== 运行时复杂性度量 ===		=== 运行时复杂性度量 ===

@@ 第214行： / 第214行： @@
 <br>
-===经验增长规律 Empirical orders of growth===
+===经验增长规律 ===
+假设算法运行时间遵循幂律规则，''{{math|t &asymp; k n<sup>a</sup>}}''，系数''a''可以通过对一些问题规模点<math>\{n_1, n_2\}</math>的运行时间<math>\{t_1, t_2\}</math>进行经验测量，并计算出𝑡<math>t_2/t_1 = (n_2/n_1)^a</math>，从而得到系数<math>a = \log(t_2/t_1) / \log(n_2/n_1)</math>。
+换言之，这衡量了在某个规模点上，执行时间与问题大小的双对数曲线 log-log plot上经验线的斜率。如果增长顺序确实遵循幂律（因此双对数曲线图上的直线确实是一条直线），那么a的经验值将在不同的范围内将保持不变，如果不是，它将发生改变（而且这条线是一条曲线），但仍然可以用来比较任何两种给定算法的经验局部增长顺序。应用于下表：

@@ 第222行： / 第222行： @@
 Assuming the execution time follows power rule, , the coefficient a can be found  by taking empirical measurements of run time <math>\{t_1, t_2\}</math> at some problem-size points <math>\{n_1, n_2\}</math>, and calculating <math>t_2/t_1 = (n_2/n_1)^a</math> so that <math>a = \log(t_2/t_1) / \log(n_2/n_1)</math>. In other words, this measures the slope of the empirical line on the log–log plot of execution time vs. problem size, at some size point. If the order of growth indeed follows the power rule (and so the line on log–log plot is indeed a straight line), the empirical value of a will  stay constant at different ranges, and if not, it will change (and the line is a curved line) - but still could serve for comparison of any two given algorithms as to their empirical local orders of growth behaviour. Applied to the above table:
-假设算法运行时间遵循幂律规则，通过对一些问题规模点<math>\{n_1, n_2\}</math>的运行时间<math>\{t_1, t_2\}</math>进行经验测量，并计算出𝑡<math>t_2/t_1 = (n_2/n_1)^a</math>，从而得到系数<math>a = \log(t_2/t_1) / \log(n_2/n_1)</math>。
+假设算法运行时间遵循幂律规则，''{{math|t &asymp; k n<sup>a</sup>}}''，通过对一些问题规模点<math>\{n_1, n_2\}</math>的运行时间<math>\{t_1, t_2\}</math>进行经验测量，并计算出𝑡<math>t_2/t_1 = (n_2/n_1)^a</math>，从而得到系数<math>a = \log(t_2/t_1) / \log(n_2/n_1)</math>。
 换言之，这衡量了在某个规模点上，执行时间与问题大小的双对数曲线 log-log plot上经验线的斜率。如果增长顺序确实遵循幂律（因此双对数曲线图上的直线确实是一条直线），那么a的经验值将在不同的范围内将保持不变，如果不是，它将发生改变（而且这条线是一条曲线），但仍然可以用来比较任何两种给定算法的经验局部增长顺序。应用于上表：

←上一版本		2021年9月23日 (四) 13:22的版本
第17行：		第17行：


−	~~'''~~算法效率的精确（这里就不是渐近了）度量有时是可以计算的，但它们通常需要一定的关于算法特定实现的假设，这种算法被称为计算模型。一个计算模型可以用抽象计算机来定义，例如图灵机，和 / 或通过假设某些操作在单位时间内执行。'''	+	算法效率的精确（这里就不是渐近了）度量有时是可以计算的，但它们通常需要一定的关于算法特定实现的假设，这种算法被称为计算模型。一个计算模型可以用抽象计算机来定义，例如图灵机，和 / 或通过假设某些操作在单位时间内执行。'''