Space 算法的复杂度

Question

这个函数的space复杂度是不是N^2输出的是一个链表？

我正在学习 space 学校的复杂性，并且被困在这个问题上。

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

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

但是，您也在构造字符串并将它们存储在内存中。字符串 str(count) 是在每次迭代中附加到列表 l 的字符串的一部分，并且该字符串的长度为 O(log n) 因为count 是最大 n 的数字，当表示为字符串时它有 O(log n) 位数字。因此，该算法的总体 space 复杂度为 O(n log n)。

Space 算法的复杂度

Space complexity of algo

python

python-3.x

big-o

space-complexity