需要帮助定义常量内存需求

  • 时间:
  • 分类: Python

我有一个HW问题,如解决方案顶部所示. 这 事实是,我不是100％确定WTF常数内存的含义. 好吧,我 想我愿意,但我很困惑. 我的解决方案是否在 列表长度的条款i? 如果是这样,我该怎么办 改变了吗? 我确定解决方案是o(n),因为列表必须 只有一次迭代,字典是o(1),对吗? 谢谢您的帮助!! #you给出了n个数字的序列s,其值从1到 N-1. #这些数字中的一个重复一次. #(示例:{1 2 3 4 5 6 3},{4 2 1 2 3 6 5}). #写一个函数,可以使用常数找到此重复数字 #记忆和线性时间. 导入系统 i = [1,3,4,5,3] tally = {} 对于i: 如果tally.has_key(a): 打印"重复数为"+str(a) sys.exit(0) 别的: tally [a] = 1 打印"没有重复找到"

# 回答1

" Jani Yusef" 在消息中写道 新闻:D3 ***********************************@posting.google.c om ... 该程序不使用恒定内存,因为可以想象 具有多达N-1元素,其中n是该元素的数量 输入. 因此,所需的总空间是O(n),而不是O(1). 您可能会问的一个问题:整个输入序列是否一次可用? 是否允许修改其元素?
# 回答2

[Jani Yusef] 在没有重复的情况下,您也不需要获得正确的答案. 仅供参考,可以通过恒定数量的数量解决问题 内存位置,假设内存位置足够大以容纳一个 整数. 但是 持有一个整数需要与log(n), 随着输入尺寸的增加,这也会增加; 我怀疑你 讲师忽略了该细节.
# 回答3

Am Sonntag,2004年9月19日07:00 Schrieben Sie: 如果您尚未找到解决方案,请考虑一下 n*(n-1)/2 + x的序列的数量和0
# 回答4

Heiko Wundram 在消息新闻中写道: ...如果您尚未找到解决方案,请考虑序列数的属性,即n*(n*(n-1) )/2 + x,带有0
# 回答5

Am Sonntag,2004年9月19日23:28 Schrieb Jani Yusef: 好吧,实际上,正如蒂姆·彼得斯(Tim Peters)已经说过的,这个功能确实不是O(1) 空间需求,因为Len(i)和总和(i)随着O(log(n))生长...但是,好的, 您的教练可能只是忽略了这个... Heiko.
# 回答6

[Jani Yusef] 仅供参考,我想到了一个不同的(尽管相关),这是 在"一个单词"中不需要比持有N-1所需的更多位. 假设整数N-1占用O(1)空间,那么此方法也是如此: def finddup(iToble): 结果= 0 对于我,x在枚举中(可见): 结果 ^ = i ^ x 返回结果 然后,例如, 当然,持有n ** 2也有o(1)空间,但在大多数语言中 需要伪造双精度整数算术. 基于 相反,减少了ints xor's的集合 收益率0允许进行单精度操作.

标签: python

添加新评论