将辅助数组初始化为 0 是否已经算作 n 时间复杂度？

Question

对于大 O 复杂性来说非常新，我想知道您是否有一个算法，其中您有一个给定的数组，并且您初始化一个具有相同数量索引的辅助数组已经计数为 n 次，或者您只是假设这是O(1)，还是什么都没有？

Answer 1

TL;DR: 无视

长答案：这将取决于您算法的其余部分以及您想要实现的目标。通常你会在之后对数组做一些有用的事情，它至少具有与填充数组相同的时间复杂度，因此数组填充不会增加时间复杂度。此外，用 0 填充数组感觉就像初始化数组一样，因此 "real" 算法可以正常工作。不过，有些情况您可以考虑。

请注意，我在以下示例中使用了伪代码，希望您清楚算法应该做什么。另请注意，所有示例都不会对数组做任何有用的事情。只是为了表明我的观点。

假设您有以下代码：

A = Array[n]
for(i=0, i<n, i++)
    A[i] = 0
print "Hello World"

那么显然你的算法的运行时间高度依赖于 n 的值，因此应该算作线性复杂度 O(n)

另一方面，如果您有更复杂的函数，请说这个：

A = Array[n]
for(i=0, i<n, i++)
    A[i] = 0
for(i=0, i<n, i++)
    for(j=n-1, j>=0, j--)
        print "Hello World"

那么即使你考虑到填充数组的复杂度，你也会以O(n^2+2n)的复杂度结束，它等于classO(n^2)，所以它不会在这种情况下很重要。

最有趣的情况肯定是当您有不同的选项用作基本操作时。假设我们有以下代码（someFunction 是一个任意函数）：

A = Array[n*n]
for(i=0, i<n*n, i++)
    A[i] = 0
for(i=0, i*i<n, i++)
    someFunction(i)

现在就看你选择什么作为基本操作了。您选择哪一个在很大程度上取决于您想要实现的目标。假设 someFunction 是一个非常便宜的函数（关于时间复杂度）并且访问数组 A 更昂贵。那么您可能会选择 O(n^2)，因为访问数组已完成 n^2 次。另一方面，如果 someFunction 与填充数组相比代价高昂，您可能会选择它作为基本操作并使用 O(sqrt(n)).

请注意，由于第一部分（数组填充）比另一部分（someFunction）执行得更频繁，因此也可以得出这样的结论，因此哪个操作并不重要将需要更长的时间才能完成，因为在某些时候阵列填充将需要更长的时间。因此，您可能会争辩说复杂性 has 是二次方的 O(n^2) 这从理论观点来看可能是正确的。但是在现实生活中你通常会有一个你想计算的操作而不关心其他操作。

实际上，您可以考虑忽略数组填充，并在我上面提供的所有示例中考虑到它，具体取决于 print 或访问数组是否更昂贵。但我希望在前两个例子中，哪一个会增加更多的运行时间是显而易见的，因此应该被视为基本操作。

将辅助数组初始化为 0 是否已经算作 n 时间复杂度？

Does initialising an auxiliary array to 0 count as n time complexity already?

big-o

time-complexity