时间复杂度什么时候有组合数据类型，如元组或对？

Question

在哈希地图数据结构(如unordered_map In C++)中：

 unodered_map<char, int> mp = { {'a', 10}, {'b', 20} };
 if (mp.find('a') != mp.end())
     cout << "found you";

我们知道find()方法需要恒定的时间。但如果我把合成数据作为关键：

 unodered_map<tuple<char, string, int>, int> mp = { {'a', "apple", 10}, 100};
 if (mp.find( {'a', "apple", 10} ) != mp.end())
     cout << "found you";

find()方法是否仍然需要恒定的时间？现在如何评估时间复杂性？

Answer 1

通常，键中的数据字节越多，哈希函数生成值所需的时间就越长(尽管一些哈希函数并不会查看每个字节，因此可以降低大O复杂度)。可能有或多或少的字节，因为元组有更多的值，或者元组中的某些元素是可变大小的(如std::string)。类似地，使用更多的字节，测试两个键是否相等通常需要更长的时间，这是哈希表的另一个关键操作。

所以，你可以说你的表的运算与键的大小成线性关系-- O(K) --所有其他条件都是相等的。

但是，更常见的是，您感兴趣的是比较任何给定的insert/erase/find的性能与在另一种类型的容器中所需的时间进行比较，而在许多其他类型的容器中，随着添加越来越多的键，性能往往会下降。在这种情况下，人们将哈希表描述为具有摊还的平均值O(1)运算复杂度，而例如平衡二叉树可能是O(logN)，其中N是存储的元素数。

还有其他一些注意事项，例如平衡二叉树中的操作往往涉及比较(即key1 < key2)，这可能在第一个不同的字节处短路，而散列函数往往必须处理键中的所有字节。

现在，如果在您的问题域中，键的大小可能有很大的差异，那么从O(K)复杂性的角度来考虑是很有意义的，但是如果键的大小倾向于在相同的典型范围内徘徊--不管您存储的键数是多少，那么表属性被合理地表示为O(1) --去掉了接近常量的乘法因子。

我认为考虑一个熟悉的类比是有帮助的。如果你有100个朋友的名字存储在你的电话通讯录里，或者你有几百万个名字来自一个大城市的电话簿，那么你的平均名字长度可能是相当相似的，所以你可以非常合理地用"N“来讨论你的数据结构的大-O效率，而忽略它缩小或者以名字长度"K”增长的方式。

另一方面，如果您考虑将任意长度的键存储在哈希表中，而且有些人可能尝试将百科全书的XML版本放入其中，而另一些人则存储小说、诗歌或单个单词，那么键长度就会有足够的多样性，因此用K来描述不同的性能是有意义的。

同样，如果您存储二进制视频数据上的例如信息，并且有人正在考虑使用原始二进制视频数据作为哈希表键:大约8k的HDR和小时长，而其他微小的动画gifs。(一种更好的方法是生成视频数据的64+位哈希，并将其用于密钥，在大多数实际用途中，该密钥将是可靠唯一的；如果处理数十亿视频，则使用128位)。

Answer 2

理论运行时间实际上不是恒定的。只有在给定合理用例的情况下，运行时间才是恒定的。

在实现中使用散列函数。如果您为在恒定时间内运行的元组实现了(good)散列函数，则渐近运行时间 of find不受影响。