java - 有效等价语句的大 O 时间复杂度

Question

假设您有算法 1（将实例化数组中的每个元素初始化为 0）：

intArray[0] = 0;
intArray[1] = 0;
...
intArray[intArray.length - 1] = 0;

和算法2：

for( int i = 0; i < intArray.length; i++)
     intArray[i] = 0;

它们的时间复杂度是否相等？我被教导要考虑比较和分配，在我看来，算法 1intArray.length的比较比算法 2 少，因此需要一半的时间。

score 3 · Accepted Answer

它们都是 O(N)。常数因素根本不会影响复杂性（尽管它们可能会影响您在实践中选择的因素）。

为 O(N) 意味着算法的运行时间总是小于k * N一些 k。k在不同的情况下可能会有所不同。

O(N) 告诉你的只是，如果你把问题放大两倍，它会花费两倍的时间。（而对于 O(N**2) 来说，将问题放大两倍则需要四倍的时间，依此类推。）

score 0 · Accepted Answer

显然它们是 O(N)。但我想补充一点。

如果initArray在编译时没有定义，你甚至不能写第一块代码。

如果initArray是在编译时定义的，这意味着 initArray 是静态初始化的，仍然不需要像第一个代码块那样编写。

int score[]={0,0,0,0,0};

为initArray.length5，更简洁。

所以大多数时候，像第一个块这样的代码是可以避免的。

2 回答 2