以最快的方式将特定间隔的元素增加 1

Question

我有一个表示为数组的元素列表。对于给定的间隔（l，r），应该将“1”添加到这些元素中。

 for( i=l;i<=r;i++)
     A[i]++;

它工作正常。但是我正在做一个程序来查找大数阶乘的总和。 由于阶乘算法需要更高的时间复杂度，我需要降低上述步骤的时间复杂度，这需要事先进行阶乘。

Answer 1

您可以通过一次递增 2 个元素的数组值来降低时间复杂度。

我认为下面的代码会将时间复杂度从 O(n) 降低到 O(n/2)。

for(i=l; i<=r; i++)
{
if(i!=r)
A[r]++;
A[i]++;
r--;
}

解释：

从起始索引和结束索引递增数组元素值。

当两个索引相同时，索引指向中间元素。 所以我们只增加一个元素（中间元素）。