- 主题:O(1)是伪命题吗？
排序哪儿有O(1)啊？ O(n)倒是有,但是并不一定比O(nlog(n))快。
【 在 johnfader 的大作中提到: 】
: 就是面试时，问了一些排序算法，快速排序比冒泡快些。
: 如果空间换时间的话，就是排序平衡二叉树，红黑树之类，最快是hash算法。
: 然后对方说，hash也不一定是最快的，如果有碰撞，就不是O(1)了。
: ...................
--
FROM 117.107.129.*
有啊，珠排序
【 在 johnfader 的大作中提到: 】
: 就是面试时，问了一些排序算法，快速排序比冒泡快些。
: 如果空间换时间的话，就是排序平衡二叉树，红黑树之类，最快是hash算法。
: 然后对方说，hash也不一定是最快的，如果有碰撞，就不是O(1)了。
: ...................
--
FROM 114.251.196.*
位图算法不就是O（1），只适合用来查有没有
【 在 johnfader 的大作中提到: 】
: 有些公司面试问O(1)的算法？我真的服了，问这种的问题都是什么水平的？
--
FROM 139.226.122.*
确实傻逼
【 在 johnfader 的大作中提到: 】
: 有些公司面试问O(1)的算法？我真的服了，问这种的问题都是什么水平的？
--
FROM 114.249.20.*
桶排序就是O(1)的啊，基本问题。
面试官就是期望你答出桶排序，然后说明在什么情况下能用桶顺序。
【 在 johnfader 的大作中提到: 】
: 就是面试时，问了一些排序算法，快速排序比冒泡快些。
: 如果空间换时间的话，就是排序平衡二叉树，红黑树之类，最快是hash算法。
: 然后对方说，hash也不一定是最快的，如果有碰撞，就不是O(1)了。
: ...................
--
FROM 114.92.8.*
有限集的计数排序是O(n)，m以内正整数的基数排序是O(n log m)。
桶排序的分桶部分是计数排序，桶里面还要处理，距离O(1)还差得远。
排序问题O(1)不可能，但查询问题在特定条件下有可能。
【 在 RunningOn 的大作中提到: 】
: 桶排序就是O(1)的啊，基本问题。
: 面试官就是期望你答出桶排序，然后说明在什么情况下能用桶顺序。
:
: ...................
--
FROM 221.221.160.*
排序为啥有hash？
【 在 johnfader 的大作中提到: 】
: 就是面试时，问了一些排序算法，快速排序比冒泡快些。
: 如果空间换时间的话，就是排序平衡二叉树，红黑树之类，最快是hash算法。
: 然后对方说，hash也不一定是最快的，如果有碰撞，就不是O(1)了。
: ...................
--
FROM 61.149.244.250
实际也不存在（假设不对原始数据集有限制）的 O(1)查询算法
【 在 milksea 的大作中提到: 】
: 有限集的计数排序是O(n)，m以内正整数的基数排序是O(n log m)。
: 桶排序的分桶部分是计数排序，桶里面还要处理，距离O(1)还差得远。
: 排序问题O(1)不可能，但查询问题在特定条件下有可能。
--
FROM 120.244.162.*
当然，自然数写出来就是O(log n)的了。现实一般是有限的。
【 在 lushan5436 的大作中提到: 】
: 实际也不存在（假设不对原始数据集有限制）的 O(1)查询算法
: 【 在 milksea 的大作中提到: 】
: : 有限集的计数排序是O(n)，m以内正整数的基数排序是O(n log m)。
: ...................
--
FROM 221.221.160.*
是我记错了定义？
不管2n还是3n都是O（n）吧
所以不管是一次两次还是10次
都是O（1）啊
除非另外有个复杂度m是hash表的冲突链平均长度
那么复杂度是O（m）
用key值的数量n衡量就是O（1）也就是常量复杂度
【 在 ylh0315 的大作中提到: 】
: 对，降低碰撞率就可以接近O1。
--
FROM 223.72.64.*