在评估使用必须初始化的数组的算法的时间复杂度时，通常表示为O(k)。其中 k 是数组的大小。
例如，计数排序 的时间复杂度为 O(n + k)。
但是当数组自动初始化时会发生什么，就像在 Java 或 PHP 中一样。可以公平地说 Java(或 PHP...)中的计数排序(或任何其他需要初始化数组的算法)的时间复杂度为 O(n)?
最佳答案
你在说这个吗 http://en.wikipedia.org/wiki/Counting_sort其时间复杂度为 O(n + k)？
您必须记住，时间复杂度是针对没有缓存和资源限制的理想机器确定的，并且独立于特定语言或机器的实际执行方式。
时间复杂度还是O(n + k)
但是在真实机器中，初始化可能比递增更有效，所以 n 和 k 不能直接比较。初始化模式类似于顺序且非常高效(n)。例如，如果计数是 int 类型，则 CPU 可以使用 long 或 128 位寄存器来执行初始化。
计数的访问模式可能是相对随机的，对于较大的 k 值可能会慢得多。 (最多慢 10 倍)
关于java - 使用自动初始化数组的算法中的复杂性测量，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/7786476/