算法的空间复杂度

Question

这个函数的空间复杂度是N^2，因为输出是一个链表吗？

我正在学校学习空间复杂性，并被困在这个问题上。

def myHealthcare(record):
l2=[]
count=0 # num of records generated and the specific time 
for i in range(record):
l=[]
now = datetime.datetime.now()
ts = now.strftime("%d/%m/%Y %H:%M:%S") # str timestamp 
ts=ts +' '+str(count)
l.append(ts)
l.append(rand.randint(36,39)) #temp
l.append(rand.randint(55,100)) #hr
l.append(rand.randint(55,100)) #Pulse
l.append(rand.randint(120,121)) #bp
l.append(rand.randint(11,17)) #respiratory rate
l.append(rand.randint(93,100)) #oxygen sat
l.append(round(rand.uniform(7.1,7.6),1)) #pH
l2.append(l)
count+=1
return l2

Answer 1

链表的空间复杂度不是二次的;每个链表节点占用恒定量的辅助内存，因此整个数据结构使用的辅助内存为 O(n(，其中n是节点数。

但是，您还构造字符串并将其存储在内存中。字符串str(count)是字符串的一部分，该字符串在每次迭代时附加到列表l，此字符串的长度为 O(log n(，因为count是一个最多 n 的数字，并且在表示为字符串时具有 O(logn( 数字。因此，该算法的整体空间复杂度为 O(n logn(。