为什么在渐进分析中忽略常量? [英] Why are constants ignored in asymptotic analysis?

问题描述

为什么在渐进分析中忽略常量?

解决方案

常量因子被忽略，因为在考虑常量因子时，运行时间和内存消耗(这两个属性通常使用O表示法最经常测量)很难推理.

如果我们定义U( f(n) )为所有函数g的集合，对于该函数存在一个N，使得对于所有N > n: g(n) <= f(n)(即与O相同，但没有常数因子)，则为很难证明算法的运行时间在U( f(n) )中比在O( f(n) )中.

一方面，我们需要一个精确的单位来测量运行时间.使用CPU指令作为基本单元是可行的，但这取决于算法的确切实现方式以及运行该处理器的处理器体系结构.

内存消耗类似:同一算法的不同实现在内存消耗方面会有所不同(按恒定因子).此外，如果实现使用大量指针，则同一实现将在64位计算机上使用的内存大约是32位计算机上的两倍.但是说使用32位Intel PC在O(23 * n)中使用此C代码实现该算法的内存消耗之类的东西，在64位PC在O(42 * n)中的这种说法"之类的话就没用了.

忽略常量使我们能够以与实现和平台无关的方式推理算法的属性.

Why are constants ignored in asymptotic analysis?

解决方案

Constant factors are ignored because running time and memory consumption (the two properties most often measured using the O-notation) are much harder to reason about when considering constant factors.

If we define U( f(n) ) to be the set of all function g for which there exists an N such that for all N > n: g(n) <= f(n) (i.e. the same as O without the constant factor), it is much harder to show that an algorithm's running time is in U( f(n) ) than O( f(n) ).

For one thing, we'd need an exact unit for measuring running time. Using a CPU instruction as the basic unit would work, but that'd depend on the exact implementation of the algorithm as well as the processor architecture it runs on.

It's similar for memory consumption: different implementations of the same algorithm will differ in their memory consumption (by a constant factor). Further if an implementation uses a lot of pointers, the same implementation will use about twice as much memory on a 64-bit machine than on a 32-bit machine. But saying things like "this algorithm's memory consumption, when implemented using this C-code, is in O(23 * n) on a 32-bit Intel PC. It's in O(42 * n) on a 64-bit PC" is just not useful.

Ignoring constants allows us to reason about the properties of an algorithm in an implementation- and platform-independent manner.

这篇关于为什么在渐进分析中忽略常量?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！