登录
  • #刷题

一个‌‌‍‍‌‌‍‌‌‌‌‍‌‌‍‌‍‍‍‍‌‌‌‍‍‍‌‍‍‍‌‍space complexity的问题

charlieyan
475
2
比如longest increasing substring这个简单的问题,time complexity没有任何争议,最优解O(n). 但是space complexity呢。如果只需要返回起始和终点位置,是O(1)。但是如果需要返回整个substring,是O(n), 对吗?

即使不考虑返回的数据结构,在程序过程中如果用到slicing,比如a[i,j],有人说Python需要建立一个隐形的序列,所以space已经是O(n)了。

你们怎么看这个问题?Python隐形建立的东西算在space complexity里面吗?程序确实在使用这些空间。

最后,农民求大米看面经!
2条回复
热度排序

发表回复