具有元组或对等复合数据类型时的时间复杂度？
Time complexity when have composite data type such as tuple or pair?
在C++中的unordered_map等Hash map数据结构中：
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() 方法是否仍需要常数时间？现在如何评估时间复杂度？
理论上的 运行 时间实际上并不恒定。在给定合理的用例的情况下，运行 时间仅在平均情况下是恒定的。
find 中的 hash function is used in the implementation. If you implement a (good) hash function for your tuple that runs in constant time, the asymptotic running time 未受影响。
一般而言，密钥中的数据字节越多，哈希函数生成值所需的时间就越长（尽管某些哈希函数不会查看每个字节，因此可以降低大 O 复杂性） .可能会有更多或更少的字节，因为元组具有更多值，或者元组中的某些元素大小可变（如 std::string）。同样，随着字节数的增加，通常需要更长的时间来测试两个键是否相等，这是哈希 tables.
的另一个关键操作
因此，您可以说您的 table 操作随键的大小线性扩展 - O(K) - 所有其他条件都相同。
但是，更多时候，您有兴趣比较任何给定 insert/erase/find 的性能与在另一种类型的容器中需要多长时间的比较，而在许多其他类型的容器中，性能倾向于随着您添加越来越多的密钥而降级。这就是人们将哈希 table 描述为通常具有分摊平均情况 O(1) 操作复杂性的地方，而例如平衡二叉树可能是 O(logN)，其中 N 是存储的元素数。
还有一些其他的考虑，例如平衡二叉树中的操作往往涉及比较（即key1 < key2），这可能会在第一个不同的字节处短路，而哈希函数往往会必须处理密钥中的所有字节。
现在，如果在您的问题域中，键的大小可能变化很大，那么根据 O(K) 复杂度来思考是有意义的，但如果键的大小倾向于徘徊在相同的典型范围内 -无论您存储的密钥数量如何，table 属性 都可以合理地表示为 O(1) - 删除接近常数的乘法因子。
我认为考虑一个熟悉的类比会有所帮助。如果您的 phone 通讯录中存储了 100 个朋友的名字，或者您有数百万来自大城市的 phone 通讯录中的名字，那么名字的平均长度可能非常相似，因此您可以非常合理地用“N”来谈论数据结构的大 O 效率，而忽略它随着名称长度“K”收缩或增长的方式。
另一方面，如果您考虑在散列 table 中存储任意长度的键，有些人可能会尝试放入 XML 版本的百科全书，而其他人则存储小说、诗歌或单个单词，那么密钥长度有足够多的变化，可以用 K 来描述不同的性能。
如果您正在存储关于二进制视频数据的信息，并且有人正在考虑使用原始二进制视频数据作为散列 table 键，则同样如此：一些 8k HDR 和数小时长，以及其他微小的动画 gif . （更好的方法是生成视频数据的 64 位以上的哈希值并将其用作密钥，对于大多数实际用途而言，该密钥将可靠地唯一；如果处理数十亿个视频，则使用 128 位）。
在C++中的unordered_map等Hash map数据结构中：
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() 方法是否仍需要常数时间？现在如何评估时间复杂度？
理论上的 运行 时间实际上并不恒定。在给定合理的用例的情况下，运行 时间仅在平均情况下是恒定的。
find 中的 hash function is used in the implementation. If you implement a (good) hash function for your tuple that runs in constant time, the asymptotic running time 未受影响。
一般而言，密钥中的数据字节越多，哈希函数生成值所需的时间就越长（尽管某些哈希函数不会查看每个字节，因此可以降低大 O 复杂性） .可能会有更多或更少的字节，因为元组具有更多值，或者元组中的某些元素大小可变（如 std::string）。同样，随着字节数的增加，通常需要更长的时间来测试两个键是否相等，这是哈希 tables.
因此，您可以说您的 table 操作随键的大小线性扩展 - O(K) - 所有其他条件都相同。
但是，更多时候，您有兴趣比较任何给定 insert/erase/find 的性能与在另一种类型的容器中需要多长时间的比较，而在许多其他类型的容器中，性能倾向于随着您添加越来越多的密钥而降级。这就是人们将哈希 table 描述为通常具有分摊平均情况 O(1) 操作复杂性的地方，而例如平衡二叉树可能是 O(logN)，其中 N 是存储的元素数。
还有一些其他的考虑，例如平衡二叉树中的操作往往涉及比较（即key1 < key2），这可能会在第一个不同的字节处短路，而哈希函数往往会必须处理密钥中的所有字节。
现在，如果在您的问题域中，键的大小可能变化很大，那么根据 O(K) 复杂度来思考是有意义的，但如果键的大小倾向于徘徊在相同的典型范围内 -无论您存储的密钥数量如何，table 属性 都可以合理地表示为 O(1) - 删除接近常数的乘法因子。
我认为考虑一个熟悉的类比会有所帮助。如果您的 phone 通讯录中存储了 100 个朋友的名字，或者您有数百万来自大城市的 phone 通讯录中的名字，那么名字的平均长度可能非常相似，因此您可以非常合理地用“N”来谈论数据结构的大 O 效率，而忽略它随着名称长度“K”收缩或增长的方式。
另一方面，如果您考虑在散列 table 中存储任意长度的键，有些人可能会尝试放入 XML 版本的百科全书，而其他人则存储小说、诗歌或单个单词，那么密钥长度有足够多的变化，可以用 K 来描述不同的性能。
如果您正在存储关于二进制视频数据的信息，并且有人正在考虑使用原始二进制视频数据作为散列 table 键，则同样如此：一些 8k HDR 和数小时长，以及其他微小的动画 gif . （更好的方法是生成视频数据的 64 位以上的哈希值并将其用作密钥，对于大多数实际用途而言，该密钥将可靠地唯一；如果处理数十亿个视频，则使用 128 位）。