我真的很困惑大O,大欧米茄和大Theta符号之间的差异.
我知道大O是上界,大欧米茄是下界,但大Ө(theta)究竟代表什么？
我读过它意味着紧张,但这意味着什么？
当给定一组静态对象(在某种意义上是静态的,一旦加载它很少会发生变化),需要重复的并发查找以及最佳性能,哪个更好,一个HashMap或一个二进制搜索使用一些自定义比较器的数组？
答案是对象或结构类型的函数吗？哈希和/或平等功能表现？哈希的独特性？清单大小？ Hashset尺寸/尺寸？
我正在看的集合的大小可以是500k到10m之间的任何地方 - 这些信息很有用.
虽然我正在寻找一个C#答案,但我认为真正的数学答案不在于语言,所以我不包括那个标签.但是,如果需要注意C#特定的事情,那么需要该信息.
我正在查看HashMapJava 7 中的源代码,我看到该put方法将检查是否已存在任何条目,如果它存在,那么它将用新值替换旧值.
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
所以,基本上它意味着给定密钥总是只有一个条目,我也通过调试看到了这一点,但如果我错了,那么请纠正我.
现在,由于给定键只有一个条目,为什么该get方法有FOR循环,因为它可以简单地直接返回值？
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
return e.value;
} …我对哈希表的时间复杂性感到困惑很多文章表明它们是"摊销的O(1)"而不是真正的命令O(1)这在实际应用中意味着什么.哈希表中的操作的平均时间复杂度是多少,实际实现中不是理论上的,为什么操作不正确O(1)？
查找仅在字符串中出现一次的第一个字符的最快方法是什么？
在我作为日常工作的一部分工作的一些项目中,我需要访问非常大的JS对象中的数据(大约数千个键值对).我正在努力提高代码的效率,所以我提出了几个问题:
obj.fieldvs obj[field])考虑到问题的一个简单实现,我正在寻找一种更快的方法来找到Python列表中最常见的单词.作为Python访谈的一部分,我收到的反馈是,这种实现效率很低,基本上都是失败的.后来,我尝试了很多我发现的算法,只有一些基于堆栈的解决方案速度稍微快一些,但不是绝大多数(当缩放到数千万个项目时,heapsearch的速度提高了大约30%;在千万倍的长度上,它几乎是相同;使用timeit).
def stupid(words):
freqs = {}
for w in words:
freqs[w] = freqs.get(w, 0) + 1
return max(freqs, key=freqs.get)
由于这是一个简单的问题而且我有一些经验(虽然我无处算法大师或竞争编码器)我很惊讶.
当然,我想提高我的技能并学习解决问题的更好方法,所以你的意见将得到赞赏.
澄清重复状态:我的观点是找出实际上是否有更多(渐近)更好的解决方案,其他类似的问题已经选择了一个不太好的答案.如果这还不足以使问题变得独一无二,那么当然要关闭这个问题.
更新
谢谢大家的意见.关于访谈情况,我仍然认为手写搜索算法是预期的(可能更有效)和/或审阅者从另一种语言的角度评估代码,具有不同的常数因素.当然,每个人都可以拥有自己的标准.
对我来说重要的是验证我是否完全无能为力(我的印象是我不是)或者通常只写不是最好的代码.仍然有可能存在更好的算法,但如果它在这里为社区隐藏了几天,我就可以了.
我正在选择最受欢迎的答案 - 这样做似乎是公平的,尽管不止一个人提供有用的反馈意见.
次要更新
看起来使用defaultdict比使用'get'方法有明显的优势,即使它是静态别名的.
假设我的100.000文件系统中有很多目录(比方说),并且每个目录中都有相似数量的目录.每个目录可以包含任意数量的文件,但通常不会超过几个.该结构变为恒定深度(10).
我的问题是,如果我从这个目录结构中读取一个文件,那么时间复杂度(在读取操作中)是否存在差异:/dir-34/dir-215/dir-345/file1使用Paths.get() 与从这样的简单文件系统读取文件相比:
/dir1
/dir2
/dir3
file1
/dir4
file2
注意:这只是一个理论问题我只想知道我尝试打开文件的目录中的目录/文件数是否对读取操作的速度有任何影响.
我不明白如果存储桶的数量恒定，那么哈希表如何进行恒定时间查找。假设我们有 100 个桶和 1,000,000 个元素。这显然是 O(n) 查找，这就是理解非常大的 n 值时事物的行为方式的复杂性所在。因此，哈希表永远不是常量查找，它始终是 O(n) 查找。
为什么人们说平均查找时间为 O(1)，而最坏情况下查找时间仅为 O(n)？
我知道列表与数组不同.但是,O(1)？这意味着访问列表中的元素与访问dict中的元素一样快,我们都知道这不是真的.我的问题是基于这份文件:
Run Code Online (Sandbox Code Playgroud)list ---------------------------- | Operation | Average Case | |-----------|--------------| | ... | ... | |-----------|--------------| | Get Item | O(1) | ----------------------------
而这个答案:
列表中的查找是O(n),字典中的查找是分摊的O(1),关于数据结构中的项目数.
如果第一个文档是真的,那么为什么访问一个dict比访问列表更快,如果它们具有相同的复杂性？
有人可以对此作出明确的解释吗？我会说它总是取决于列表/字典的大小,但我需要更多的洞察力.