当要计算使用必须初始化的数组的算法的时间复杂度时，通常表示为O(k)。其中k为数组的大小。
例如，计数排序的时间复杂度为O(n + k)。
但是当数组被自动初始化时发生了什么，就像在Java或PHP中一样。是否可以说计数排序(或任何其他需要初始化数组的算法)在Java(或PHP…)中具有O(n)的时间复杂度?
你是在说这个时间复杂度为0 (n + k)的http://en.wikipedia.org/wiki/Counting_sort吗?
你必须记住，时间复杂度是由一个理想的机器决定的，它没有缓存，资源限制，与特定语言或机器的实际运行方式无关。
时间复杂度仍为O(n + k)
然而，在实际机器中，初始化可能比递增更有效，因此n和k不能直接比较。初始化的模式是顺序的，非常高效(n)。例如，如果计数类型为int，则CPU可能使用long或128位寄存器来执行初始化。
计数的访问模式可能是相对随机的，并且对于较大的k值可能会慢得多。(最多慢10倍)
实际上应该是O(n+k)
因此，如果n的阶数高于k(在计数排序中有许多重复)，它可以在时间复杂度中被丢弃，使其成为O(n)
自动初始化不是免费的，您必须考虑它，所以它仍然是O(n + k)