自初始化阵列算法中的复杂度度量

Question

当要评估使用必须初始化的数组的算法的时间复杂度时，通常用O(k)表示。其中k是数组的大小。

例如，计数排序的时间复杂度为O(n + k)。

但是，当数组被自动初始化时会发生什么，比如在Java或PHP中。公平地说，在Java (或PHP.)中计数排序(或任何其他需要初始化数组的算法)是否公平？具有O(n)的时间复杂性

Answer 1

你是说这个时间复杂度为O(n + k)的http://en.wikipedia.org/wiki/Counting_sort吗？

您必须记住，时间复杂性是为一个理想化的机器确定的，它没有缓存、资源约束，并且独立于特定语言或机器的实际执行方式。

时间复杂度仍然是O(n + k)。

然而，在真正的机器上，初始化可能比增量更有效，因此n和k并不是直接可比的。初始化的模式是顺序的和非常有效的( n)。例如，如果计数是int类型，则CPU可以使用long或128位寄存器来执行初始化。

用于计数的访问模式可能是相对随机的，对于较大的k值则可能要慢得多。(慢10倍)

Answer 2

实际上是O(n+k)

因此，如果n的阶数比k (计数排序中的许多重复项)高，则可以在时间复杂性中丢弃它，使其成为O(n)。

Answer 3

自动初始化不是免费的，无论如何您必须考虑它，所以它仍然是O(n + k)。