我有一个基本问题，关于使用哈希表而不是二叉搜索树(或平衡树)时基本操作的时间复杂度。
不幸的是，在基础算法类(class)中，这是我学习的唯一类型，我了解到理想情况下，使用哈希表查找/插入的时间复杂度是O(1)。对于二叉(搜索)树，其时间复杂度为 O(log(n))，其中“n”是输入对象的“数量”。到目前为止，就渐进访问时间而言，哈希表是赢家(我猜)。
现在将“n”作为数据结构数组的大小，将“m”作为要存储在数组中的不同输入对象(值)的数量。 DS。
对我来说，数据结构操作(例如查找)的时间复杂度存在模糊性。真的有可能在“n”中以“计算/评估”复杂度常数时间进行散列吗？具体来说，如果我们知道所存储的对象有“m”不同值，那么哈希函数仍然可以比“Omega (log(m)”运行得更快吗？ )”？ 如果不是，那么我会声称非平凡应用程序的复杂性必须为 O( log ( n ) ) )，因为实际上“n”和“m”并没有太大不同。
我看不出找到这样的函数的方法。例如，取 m= 2^O( k) 为长度为“k”字节的不同字符串的总数。哈希函数必须遍历所有“k”字节，即使只需要恒定的时间来计算每个字节，那么对输入进行哈希处理所需的总时间为 Omega( k ) = Omega( log( m) ).
话虽如此，对于潜在输入数量与表格大小相当的情况，例如“m”几乎等于“n” ，哈希复杂度对我来说看起来不像常数时间。
最佳答案
您的担忧是有道理的，但我认为您还遗漏了第二点。如果在计算 BST 时间复杂度时将查看所有输入字节所需的时间考虑在内，则需要将现有的 O(log n) 时间乘以每次比较所需的时间，即将为 O(log m)。然后，您将在 BST 中获得 O(log n log m) 的搜索时间。
通常，BST 和哈希表的时间复杂度状态不是实时复杂度，而是基础数据类型上的“基本操作”的数量。例如，哈希表按照预期执行 O(1) 次哈希并比较基础数据类型。 BST 将对基础数据类型进行 O(log n) 比较。如果这些比较或哈希不需要花费 O(1) 时间，那么执行查找所需的时间将不是 O(1)(对于哈希表)或 O(log n)(对于 BST)。
在某些情况下，我们对机器的工作方式做出假设，这让我们可以方便地忽略处理输入位所需的时间。例如，假设我们对 0 到 2k 之间的数字进行哈希处理。如果我们假设我们有 transdichotomous machine model ，那么假设每个机器字至少为 Ω(k) 位，我们可以在 O(1) 时间内对机器字执行操作。这意味着我们可以在时间 O(1) 而不是时间 O(k) 的时间内对 k 位执行哈希，因为我们假设字大小作为问题集的函数而增长。
希望这有帮助!
关于data-structures - 为什么散列和 BST 的复杂性不考虑处理 key 字节所需的时间？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/20207168/