对于一项作业，我应该编写一种算法，该算法最多允许我使用n + O（log（n））个额外的内存位（有关该算法的实际细节在这里并不重要），其中n是输入数组的大小。
我提交了通过所有测试用例的算法；但是，我的评分员说我正在使用n + O（log（n））位以上的内存。他们的理由是，作为算法的一部分，我将数量（n * i）添加到数组中的每个元素（其中i = 1，2，3，... n。i是a中的索引变量）环）。他们说对于非常大的n值，我将使用更多的内存来存储较大的数字。
这导致我遇到以下问题：是的，通过将n * i加到每个数字上，我的空间复杂度是否超过n + O（log（n））位？我在算法分析方面的经验非常有限，但是我个人从未见过将大量存储作为增加空间复杂性的理由。但是让我们说说它确实增加了复杂性-我会使用n + O（log（n））位吗？
我想提出一个挑战的论据，但我只想确保自己在做对之前是对的。
让b1是每个数字的位数，然后再加上(i*n)，然后是b2。
不平等（1）：
b2-b1 <= log(n*n) = 2log(n)证明（1）：
Lemma 1: binary number is the best coding scheme for integers in memory. Lemma 2: The sum of 2 integers always has the result shorter than the sum of each number's sizes.来自不等式（1），
[在极端情况下，如果为b1 -> 0，则为b2 = 2log(n)，因此空间的增加为2nlog(n)。总空间为C + O(nlog(n))
免责声明：这不能证明您的问题，因为我不知道您一开始为每个数字使用了多少位。