- 主题:O(1)是伪命题吗?
是我记错了定义?
不管2n还是3n都是O(n)吧
所以不管是一次两次还是10次
都是O(1)啊
除非另外有个复杂度m是hash表的冲突链平均长度
那么复杂度是O(m)
用key值的数量n衡量就是O(1)也就是常量复杂度
【 在 ylh0315 的大作中提到: 】
: 对,降低碰撞率就可以接近O1。
--
FROM 223.72.64.*
说的是hash查询呀,没有碰撞的话就是O(1)啊,100%碰撞就是O(n)。
【 在 SHUOT 的大作中提到: 】
: 是我记错了定义?
: 不管2n还是3n都是O(n)吧
: 所以不管是一次两次还是10次
: ...................
--
FROM 221.221.48.*
讨论算法复杂度都是有假定前提的吧
理论碰撞一定有,不影响算法是O(1)
因为假定的hash函数冲突链长度和n无关
如果是相关的那就得指明
比如hash函数只有常数个值是O(n)
hash函数值范围是n/lg(n)的话复杂度就是O(lgn)
而不能说条件是碰撞发生了就不是O(1)
【 在 ylh0315 的大作中提到: 】
: 说的是hash查询呀,没有碰撞的话就是O(1)啊,100%碰撞就是O(n)。
--
FROM 223.72.64.*
数学方法就是o1啊,你可以回答,循环求和改高斯公式
--
FROM 124.64.19.*