| 第50行： |
第50行： |
| | | | |
| | | | |
| − | == 成本模型 Cost models == | + | == 成本模型 == |
| − | | |
| − | Time efficiency estimates depend on what we define to be a step. For the analysis to correspond usefully to the actual execution time, the time required to perform a step must be guaranteed to be bounded above by a constant. One must be careful here; for instance, some analyses count an addition of two numbers as one step. This assumption may not be warranted in certain contexts. For example, if the numbers involved in a computation may be arbitrarily large, the time required by a single addition can no longer be assumed to be constant.
| |
| − | | |
| − | Time efficiency estimates depend on what we define to be a step. For the analysis to correspond usefully to the actual execution time, the time required to perform a step must be guaranteed to be bounded above by a constant. One must be careful here; for instance, some analyses count an addition of two numbers as one step. This assumption may not be warranted in certain contexts. For example, if the numbers involved in a computation may be arbitrarily large, the time required by a single addition can no longer be assumed to be constant.
| |
| − | | |
| | 时间效率的估计取决于我们对步骤的定义。为了使分析有效地对应于实际执行时间，执行一个步骤所需的时间必须保证一个常数。这里需要注意的是，例如，有些分析把两个数字的相加计算为一个步骤。在某些情况下，这种假设可能是不正当的。例如，如果计算中涉及的数字可能是任意大的，那么单个加法所需的时间就不能再假定为常数。 | | 时间效率的估计取决于我们对步骤的定义。为了使分析有效地对应于实际执行时间，执行一个步骤所需的时间必须保证一个常数。这里需要注意的是，例如，有些分析把两个数字的相加计算为一个步骤。在某些情况下，这种假设可能是不正当的。例如，如果计算中涉及的数字可能是任意大的，那么单个加法所需的时间就不能再假定为常数。 |
| | | | |
| | | | |
| − | | + | 通常使用两种成本模型:<ref name="AhoHopcroft1974">{{cite book|author1=Alfred V. Aho|author2=John E. Hopcroft|author3=Jeffrey D. Ullman|title=The design and analysis of computer algorithms|url=https://archive.org/details/designanalysisof00ahoarich|url-access=registration|year=1974|publisher=Addison-Wesley Pub. Co.}}, section 1.3</ref><ref name="Hromkovič2004">{{cite book|author=Juraj Hromkovič|title=Theoretical computer science: introduction to Automata, computability, complexity, algorithmics, randomization, communication, and cryptography|url=https://books.google.com/books?id=KpNet-n262QC&pg=PA177|year=2004|publisher=Springer|isbn=978-3-540-14015-3|pages=177–178}}</ref><ref name="Ausiello1999">{{cite book|author=Giorgio Ausiello|title=Complexity and approximation: combinatorial optimization problems and their approximability properties|url=https://books.google.com/books?id=Yxxw90d9AuMC&pg=PA3|year=1999|publisher=Springer|isbn=978-3-540-65431-5|pages=3–8}}</ref><ref name=Wegener20>{{Citation|last1=Wegener|first1=Ingo|title=Complexity theory: exploring the limits of efficient algorithms|publisher=[[Springer-Verlag]]|location=Berlin, New York|isbn=978-3-540-21045-0|year=2005|page=20|url=https://books.google.com/books?id=u7DZSDSUYlQC&pg=PA20}}</ref><ref name="Tarjan1983">{{cite book|author=[[Robert Endre Tarjan]]|title=Data structures and network algorithms|url=https://books.google.com/books?id=JiC7mIqg-X4C&pg=PA3|year=1983|publisher=SIAM|isbn=978-0-89871-187-5|pages=3–7}}</ref> |
| − | Two cost models are generally used:<ref name="AhoHopcroft1974">{{cite book|author1=Alfred V. Aho|author2=John E. Hopcroft|author3=Jeffrey D. Ullman|title=The design and analysis of computer algorithms|url=https://archive.org/details/designanalysisof00ahoarich|url-access=registration|year=1974|publisher=Addison-Wesley Pub. Co.}}, section 1.3</ref><ref name="Hromkovič2004">{{cite book|author=Juraj Hromkovič|title=Theoretical computer science: introduction to Automata, computability, complexity, algorithmics, randomization, communication, and cryptography|url=https://books.google.com/books?id=KpNet-n262QC&pg=PA177|year=2004|publisher=Springer|isbn=978-3-540-14015-3|pages=177–178}}</ref><ref name="Ausiello1999">{{cite book|author=Giorgio Ausiello|title=Complexity and approximation: combinatorial optimization problems and their approximability properties|url=https://books.google.com/books?id=Yxxw90d9AuMC&pg=PA3|year=1999|publisher=Springer|isbn=978-3-540-65431-5|pages=3–8}}</ref><ref name=Wegener20>{{Citation|last1=Wegener|first1=Ingo|title=Complexity theory: exploring the limits of efficient algorithms|publisher=[[Springer-Verlag]]|location=Berlin, New York|isbn=978-3-540-21045-0|year=2005|page=20|url=https://books.google.com/books?id=u7DZSDSUYlQC&pg=PA20}}</ref><ref name="Tarjan1983">{{cite book|author=[[Robert Endre Tarjan]]|title=Data structures and network algorithms|url=https://books.google.com/books?id=JiC7mIqg-X4C&pg=PA3|year=1983|publisher=SIAM|isbn=978-0-89871-187-5|pages=3–7}}</ref>
| |
| − | | |
| − | Two cost models are generally used:
| |
| − | | |
| − | 通常使用两种成本模型:
| |
| − | | |
| − | * the '''uniform cost model''', also called '''uniform-cost measurement''' (and similar variations), assigns a constant cost to every machine operation, regardless of the size of the numbers involved
| |
| − | | |
| − | 统一成本模型：也称为“统一成本计量”（和类似的变体），为每台机器操作分配一个固定的算法消耗，与涉及的数量大小无关；
| |
| − | | |
| − | * the '''logarithmic cost model''', also called '''logarithmic-cost measurement''' (and similar variations), assigns a cost to every machine operation proportional to the number of bits involved
| |
| − | | |
| − | “对数成本模型”，也称为“对数成本测量”（及类似变体），为每台机器操作分配一个与所涉及的位数成比例的成本；
| |
| | | | |
| | | | |
| | + | * 统一成本模型：也称为“统一成本计量”（和类似的变体），为每台机器操作分配一个固定的算法消耗，与涉及的数量大小无关； |
| | | | |
| − | The latter is more cumbersome to use, so it's only employed when necessary, for example in the analysis of [[arbitrary-precision arithmetic]] algorithms, like those used in [[cryptography]].
| + | * 对数成本模型：也称为“对数成本测量”（及类似变体），为每台机器操作分配一个与所涉及的位数成比例的成本； |
| | | | |
| − | The latter is more cumbersome to use, so it's only employed when necessary, for example in the analysis of arbitrary-precision arithmetic algorithms, like those used in cryptography.
| |
| | | | |
| | 后者使用起来比较麻烦，所以只有在必要的时候才会使用，例如在分析高精度计算算法时，就像那些在密码学中使用的算法。 | | 后者使用起来比较麻烦，所以只有在必要的时候才会使用，例如在分析高精度计算算法时，就像那些在密码学中使用的算法。 |
| | | | |
| | | | |
| | + | 而一个经常被我们忽略的关键点是，常见问题的下界通常是给定一个计算模型，这个模型比你在实践中可以使用的操作集更加有限，因此存在一些算法的效率比我们认为的下界要更快。<ref>[https://cstheory.stackexchange.com/q/608 Examples of the price of abstraction?], cstheory.stackexchange.com</ref> |
| | | | |
| − | A key point which is often overlooked is that published lower bounds for problems are often given for a model of computation that is more restricted than the set of operations that you could use in practice and therefore there are algorithms that are faster than what would naively be thought possible.<ref>[https://cstheory.stackexchange.com/q/608 Examples of the price of abstraction?], cstheory.stackexchange.com</ref>
| + | <br> |
| − | | |
| − | A key point which is often overlooked is that published lower bounds for problems are often given for a model of computation that is more restricted than the set of operations that you could use in practice and therefore there are algorithms that are faster than what would naively be thought possible.
| |
| − | | |
| − | 而一个经常被我们忽略的关键点是，常见问题的下界通常是给定一个计算模型，这个模型比你在实践中可以使用的操作集更加有限，因此存在一些算法的效率比我们认为的下界要更快。
| |
| | | | |
| | == 运行时分析 == | | == 运行时分析 == |