个人中心
文章发布
退出
作者热门文章
- html - 出于某种原因，IE8 对我的 Sass 文件中继承的 html5 CSS 不友好？
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景？
26
4
如果哈希表包含 N 个不同的项目，并且没有重载，那么 N 个项目的哈希值必须大约有 lg(N) 位，否则太多的项目将获得相同的哈希值。
但是通常说哈希表查找平均需要 O(1) 时间。
不可能在 O(1) 时间内生成 lg(N) 位，因此哈希表复杂度的标准结果是错误的。
我的推理有什么问题？
最佳答案
您的推理有问题的是使用了相互矛盾的“时间”定义。
当有人说在哈希表中查找需要 O(1) 时间时，通常意味着它需要 O(1) 次比较，即找到一项所需的比较次数以常数为界。在这种“时间”的概念下，用于计算散列的实际时间(如您以秒为单位测量的时间)不会导致变化。
在比较中测量时间是一种近似值，虽然它可能不像以秒为单位的测量方式那样反射(reflect)现实，但仍提供有关哈希表行为的有用信息。
对于算法的大多数渐近复杂性描述来说，这种事情是正确的:人们经常使用具有非常抽象含义的“时间”，这不是“时间”的非正式含义，但通常是“时间”的一些变体操作的数量”(操作的种类通常未说明，预计是显而易见的，或者从上下文中清楚)。
关于complexity-theory - 哈希表中的查找是 O(1) 吗？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/27127862/
26
4
0
最近我试图向我的项目经理解释一些设计不佳的代码。所有的管理器类都是单例的(“这就是我不能轻易改变它的原因”)并且代码在任何一个函数调用就足够的地方使用事件分派(dispatch)(“这就是为什么它很难
我有一个简单的问题。这里的上标加号是什么意思？ = {w ∈ {0,1} : w ∈ (0^+)(1^+)} 我做这些已经有一段时间了。这是为了制作一个非确定性的有限自动机 最佳答案 0^+ 这意味着
就目前而言，这个问题不适合我们的问答形式。我们希望答案得到事实、引用或专业知识的支持，但这个问题可能会引起辩论、争论、投票或扩展讨论。如果您觉得这个问题可以改进并可能重新打开，visit the he
引用自 Algorithms for Java (sedgwick 2003) p。 135: “我们通常在开发或调试广告时使用驱动程序” 驱动程序是什么意思？ 谷歌只是给了我大量关于编程驱动程序的信
我坚信这样一种观点，即您从学习一门新语言中获得的最重要的东西之一不是如何使用一门新语言，而是您从中获得的概念知识。我不是问你认为 Assembly 有多重要或有用，我也不关心我是否从未在我的任何实
对于example，任何图灵机都不能接受不接受其自身编码的图灵机的语言。 最佳答案 TM不能决定无限多种语言。确实，“大多数”语言是不确定的。有许多可判定的语言，但有无数种语言(因此，无数许多不可判定
关闭。这个问题不符合Stack Overflow guidelines .它目前不接受答案。 想改进这个问题？将问题更新为 on-topic对于堆栈溢出。 5年前关闭。 Improve this qu
关闭。这个问题是off-topic .它目前不接受答案。 想改善这个问题吗？ Update the question所以它是 on-topic对于堆栈溢出。 8年前关闭。 Improve this q
我已经尝试证明这很有趣 bubble_main已订购，但似乎没有任何方法有效。这里有人能帮我证明引理is_ordered (bubble_main L)请。 我只是删除了我以前的所有引理，因为似乎没有
我目前正在研究离散数学测试，其中我们正在学习Chomsky's hierarchy和识别层次结构各个级别的自动机的类型。有人告诉我，大多数计算机语言都属于层次结构的“2级和1级”，但不完全属于该级别。
在我的编程类(class)原则中，我们谈论的是不同的调用方法。我们讨论了一些: 按值调用 通过引用进行调用 按值/结果调用 和调用，名称为 我找不到有关按名称调用的工作方式的示例。有人在乎给我举个例子
关闭。这个问题需要更多focused .它目前不接受答案。 想改善这个问题吗？更新问题，使其仅关注一个问题 editing this post . 3年前关闭。 Improve this questi
需要明确的是，我不是在寻找 NaN 或无穷大，也不是在问 x/0 的答案是什么。应该是。我要找的是这个: 根据硬件中的除法方式(我不知道它是如何进行的)，如果除以除数为0的除法，并且处理器在操作中愉快
关闭。这个问题需要details or clarity .它目前不接受答案。 想改善这个问题吗？通过 editing this post 添加详细信息并澄清问题. 4年前关闭。 Improve thi
我已经阅读了几页，包括 wiki 页面 http://en.wikipedia.org/wiki/Strong_and_weak_typing处理强类型语言和弱类型语言。在大多数情况下，我想我理解其中
停机问题对于图灵完备的语言是无法解决的，对于一些非 TC 语言，比如它总是停机的正则表达式，它可以很容易地解决。 我想知道是否有任何语言既可以停止也可以不停止，但承认一种可以确定它是否停止的算法。 最
好吧，我想这完全是主观的，但我在考虑随机数生成器的熵源。大多数生成器都是用当前时间播种的，对吗？好吧，我很好奇可以使用哪些其他来源来生成完全有效的随机(松散定义)数字。 使用多个来源(例如时间 + 当
我正在学习计算复杂性类(class)，到目前为止，我的印象是它对开发人员没有太大帮助。 我可能是错的，但如果你以前走这条路，你能举一个例子来说明复杂性理论如何帮助你的工作吗？万分感谢。 最佳答案 O(
在类里面，我们学习了停机问题，图灵机，归约等。很多同学说这些都是抽象无用的概念，了解它们没有任何意义(即，一旦类(class)结束就可以忘记它们)结束并且不会丢失任何东西)。 为什么理论有用？您是否曾
在多任务系统中，某些异常情况会阻止进程或线程的执行进度。我将进程和线程简称为“进程”。其中两种情况称为死锁和活锁。 前者指的是相互阻塞的进程，从而阻止其中一个进程执行。后者指的是相互阻止进程，但实际上
我是一名优秀的程序员,十分优秀！