我试图分析该算法在最坏情况下的空间复杂性，以解决Codibility的CountNonDivisible问题。
问题陈述：
您得到了一个由N个整数组成的数组A。
对于每个数A[i]，使得0≤i<N、 我们想数数数组中不是A[i]的除数的元素。我们说这些元素是非除数。
编写一个函数，在给定这样一个数组的情况下，返回表示每个元素的非除数数量的整数。
针对以下假设编写一个高效算法：
- N是[150000]范围内的整数
- 数组A的每个元素都是在[1,2N]范围内的整数
算法(我添加了注释)：
def solution(A):
A_max = max(A) # O(1) space
count = {} # O(1) space
# Create a count of the occurrences of each element in the input array.
# O(N) space
for element in A:
if element not in count:
count[element] = 1
else:
count[element] += 1
divisors = {} # O(1) space
# O(N) space
for element in A:
divisors[element] = set([1, element])
divisor = 2 # O(1) space
# Space TBC
while divisor*divisor <= A_max:
element_candidate = divisor # O(1) space
while element_candidate <= A_max: # O(1) space
if element_candidate in divisors and not divisor in divisors[element_candidate]: # O(1) space
divisors[element_candidate].add(divisor) # O(1) space
divisors[element_candidate].add(element_candidate//divisor) # O(1) space
element_candidate += divisor # O(1) space
divisor += 1 # O(1) space
result = [0] * len(A) # O(N) space
# Space TBC
for idx, element in enumerate(A):
result[idx] = (len(A) - sum([count.get(divisor,0) for divisor in divisors[element]]))
return result
文章指出，预期最坏情况下的空间复杂度为O(N)。
但是divisorsdict需要用于存储除数集的空间。
如果dict中的每个值都是一个整数，那么我就会清楚为什么最坏情况下的空间复杂度是O(N)。但每个值都是一组整数。
因此，我认为除数集所需的总空间与除数的总数成正比。
在最坏的情况下，大约有多少除数将存储在所有这些集合中？
对于给定的N，当我们最大化存储在所有集合中的除数总数时，最坏的情况应该发生。
要做到这一点，我认为我们可以使用以下算法：
- 构造一个大小为2N的数组B，其元素等于d(n)序列中的前2N个值，即列出n的除数的序列
- 对B和Bi的元素进行排序，首先按B中的值(按降序)，然后按Bi中的值排序(也按降序)
- 然后让最坏情况的输入阵列A是由Bi中的前N个元素组成的子阵列
例如，如果N=12，则2N=24，并且在排序之前：
Bi=[1，2，3，4，5，6，7，8，9，10，11，12，13，14，15，16，17，18，19，20，21，22，23，24]
B=[1,2,2,3,2,4,4,3,4,2,6,2,4,5,2,6,2,6,4,2,8]
排序后：
Bi=[24，20，18，12，16，22，21，15，14，10，8，6，9，4，23，19，17，13，11，7，5，3，2，1]
B=[8,6,6,5,4,4,4,4,3,2,2,2,2-2,2,2,1]
并且输入阵列A=[24，20，18，12，16，22，21，15，14，10，8，6]
除数的总数是59。
我正在努力解决的问题是如何将其推广到[150000]范围内的任何N。
我假设O(N)最坏情况下的空间复杂性在某个地方由Codibility陈述/证明，但我还没能找到哪里。
我上面的分析是否正确？如果是，我将如何完成最坏情况下空间复杂性的计算？
如果不是，那么它实际上是O(N)吗？如果它是O(N)，我的分析做错了什么？
解决方案实际上不是O(N)空间，因为它将为a的每个元素存储一个除数列表。由于1..N范围内的数字的除数总数随着N的增加而增加，因此复杂性将为O(NxK)，其中K是1..N除以N的除数的平均数。
如果在返回结果之前打印sum(map(len,divisors.values()))，您会发现解决方案([1，2，3，4，5，6，7，9，10])在除数字典中的所有集合中总共有27个条目(66个条目表示1..20，111个条目表示1.30，158个条目表示1.40，依此类推，与N的比率从2.7增加到3.95)。这表明空间复杂度为O(Nxf(N))，其中f(N)是某个随N增加的函数。
简而言之，链路中的算法不满足上述O(N)空间期望。它也不满足O(NlogN)时间复杂度的期望。
如果你要使用Erathostene的筛选(如Codibility执行语句中所建议的)，你只需要存储N个元素(或更少)的计数器，因为你只需要将不同因子的倍数分布在列表中实际存在的倍数上。这将满足O(N)空间要求。
以下是建议逻辑的一个更简单的实现：
def solution2(A):
minA = max(2,min(A)) # minimum multiple
maxA = max(A) # maximum multiple
numCounts = dict.fromkeys(A,0)
for n in A: numCounts[n] += 1 # distinct counts
divCounts = numCounts.copy() # divisor counts
for n in numCounts:
for m in range(minA*n,maxA+1,n): # propagate multiples
if m in divCounts:
divCounts[m] += numCounts[m] # add factor count
return [len(A)-divCounts[n] for n in A ]
numCounts/divCounts最多包含N个条目(确保O(N)空间)。A中>N在传播循环中根本不会迭代，因此只有项<=N实际上会将它们的计数传播到倍数(以筛选方式)。
然而，这将具有大于O(NlogN)的时间复杂性，因为向倍数的传播次数可能高达：
2N/2 + 2N/3 + 2N/4 ... + 2 # e.g. A = [2,3,4...,N,2N]
相当于
2N*∑(1/i) for [i=2..n] # this is > N * log(N)