首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >问答首页 >O(1)平均时间的n个运算是否平均考虑O(n)?

O(1)平均时间的n个运算是否平均考虑O(n)?
EN

Stack Overflow用户
提问于 2013-07-03 06:42:03
回答 1查看 45关注 0票数 0

我正在学习数据结构考试,我试图解决这个问题:

给定一个n个数的数组和一个Z数,在O(n)平均时间内找到x,y(如x+y=Z )。

我的建议是将数组的内容移到哈希表中,并使用打开寻址执行以下操作:

对于每个数字,Ai在哈希表中搜索Z-Ai (每个操作平均为O(1))。最坏的情况是,执行n次搜索,O(1)次平均时间,即平均O(n)次。

我的分析正确吗?

EN

回答 1

Stack Overflow用户

发布于 2013-07-03 06:49:57

假设您是第二次遍历所有数组,是的,即O(n) * O(1) (而不是前面我说过的O(n)+O(1) )(用于平均时间的哈希查找),所以您讨论的是O(n)复杂度的算法。

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/17441323

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档