如果我使用一个最大大小为N的向量作为std：：map的键，那么键的查找时间/访问时间是O（1）还是O（N）？同样的问题，但是如果我使用大小为N的字符串，map和unordered_map都有问题吗？假设值为整数。所以我们有一个大小为N的Map，这个Map有向量键，值为整数。向量的大小也为N。时间复杂度为O（N）我在几个月前的一次采访中被问到这个问题时，我措手不及，我真的不确定，但我认为它应该是O（N）。
bybem2ql1#
一个边界是O（N * logN），因为在线性时间中的向量比较和在对数时间中的Map查找。但是你必须小心使用大O符号。另一个界是O（2 ^N）或O（ackermann（N，N）），因为O（f）是如何定义的。我怀疑最严格的边界远低于O（N * logN），因为你的键查找不会是Theta（N）。例如，如果将baaaaaaaaa与条目caaaaaaaaa进行比较，则不需要进行10次比较来确定第一个条目小于后者。你只需要一个。因此，如果map的树是大致平衡的（rb树就是这样）和你的key vector只有二进制值（0或1），那么一半的值应该从0开始，一半从1开始。这意味着在第一个分支上，一半的值将在仅~1次比较之后确定，四分之一在~2次比较之后确定，等等，八分之一在~3次比较之后确定，等等。第一个比较的成本为expected constant。我不知道其他人的行为，但我怀疑他们遵循类似的模式。因此，时间复杂度可以用比悲观O（N * logN）更好的项来近似。如果键值不是二进制的，那么边界可能会再次变得任意糟糕，所有的赌注都将被取消。
baaaaaaaaa
caaaaaaaaa
1条答案
按热度按时间bybem2ql1#
一个边界是O（N * logN），因为在线性时间中的向量比较和在对数时间中的Map查找。但是你必须小心使用大O符号。另一个界是O（2 ^N）或O（ackermann（N，N）），因为O（f）是如何定义的。
我怀疑最严格的边界远低于O（N * logN），因为你的键查找不会是Theta（N）。例如，如果将
baaaaaaaaa与条目caaaaaaaaa进行比较，则不需要进行10次比较来确定第一个条目小于后者。你只需要一个。因此，如果map的树是大致平衡的（rb树就是这样）和你的key vector只有二进制值（0或1），那么一半的值应该从0开始，一半从1开始。这意味着在第一个分支上，一半的值将在仅~1次比较之后确定，四分之一在~2次比较之后确定，等等，八分之一在~3次比较之后确定，等等。第一个比较的成本为expected constant。我不知道其他人的行为，但我怀疑他们遵循类似的模式。因此，时间复杂度可以用比悲观O（N * logN）更好的项来近似。
如果键值不是二进制的，那么边界可能会再次变得任意糟糕，所有的赌注都将被取消。