将n个值分配给大小为n O(n)的数组的时间复杂度是多少？
将n个值分配给大小为n O(n)的数组的时间复杂度是多少？
提问于 2019-05-29 17:32:34
我正在尝试哈希中的索引映射来搜索数组中的元素。线性搜索在一个大小为n的数组中搜索一个元素需要O(n)。在散列中，我们所做的基本上是通过创建一个2维的零矩阵(比如hash1000)，并在ai为正的情况下将hasha[i]重新分配为1，如果ai为负，则将hash-a[i]的时间复杂度降低到O(1)。这里ai是我们应该搜索元素的数组。
for(i=0 ;i<n ;i++)
{
if(a[i]>=0)
has[a[i]][0]=1;
else
has[-a[i]][1]=1;
}执行上面的代码需要多长时间？即使通过散列，我们的时间复杂度不也是O(n)，就像线性搜索一样吗？在二维零数组中分配n个1所消耗的时间不等于以线性方式搜索一个元素所花费的时间吗？
回答 1
Stack Overflow用户
发布于 2019-05-29 17:42:15
这里的典型做法是维护一个按散列键排序的数组，然后使用二进制搜索来定位元素，最坏情况下的时间复杂度为O(log )。
通过使用与查找现有元素相同的二进制搜索来插入新元素，可以保持排序顺序。
最后一点很重要:正如评论中指出的那样，在每次搜索之前进行排序会降低搜索时间，以至于对于小数据集，蛮力线性搜索的速度更快。但是可以消除这种开销；如果在插入新元素时保持排序顺序，则永远不需要对数组进行排序。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/56357378
复制相关文章
相似问题
腾讯云开发者
