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;

它们的时间复杂度相等吗？我被教导要考虑比较和赋值，在我看来，算法 1 应该有 intArray.length比算法 2 更少的比较，因此需要一半的时间。

Answer 1

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

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

O(N) 告诉你的只是，如果你把问题扩大一倍，那么它需要两倍的时间。 (而对于 O(N**2) 来说，将问题扩大一倍需要四倍的时间，依此类推。)