免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
› 论坛 › 程序设计 › C/C++ › 阿里实习生笔试题 一个数组中两个元素的和等于第三个元 ...
12下一页
最近访问板块 发新帖
查看: 8204 | 回复: 10
打印 上一主题 下一主题

[算法] 阿里实习生笔试题 一个数组中两个元素的和等于第三个元素的时间复杂度 [复制链接]

chinesefys

论坛徽章:
0
跳转到指定楼层
1楼 [收藏(0)] [报告]
发表于 2013-05-18 12:49 |只看该作者 |倒序浏览
判断一包含n个整数a[]中是否存在i、j、k满足a[i] + a[j] = a[k]的时间复杂度最小值是
A.O(n^2) B. O(n^2*logn) C. O(n^3) D. O(nlogn)

俺觉得是A，a[i] a[j]的组合就O(n^2)了，还得查找，大家说说想法啊
井蛙夏虫

论坛徽章:
4
白羊座 日期:2013-09-17 21:59:30技术图书徽章 日期:2013-10-12 22:16:03白羊座 日期:2013-10-14 11:01:40双子座 日期:2013-12-17 18:26:39
2楼 [报告]
发表于 2013-05-18 13:22 |只看该作者
我觉得是B
按你说的方法，组合是n^2,还要查找,查找最快logn,所以n^2*logn
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
chinesefys

论坛徽章:
0
3楼 [报告]
发表于 2013-05-18 13:36 |只看该作者
回复 2# 井蛙夏虫

兄弟，hash表查找只要O(1)啊


   
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
linux_c_py_php

论坛徽章:
4
水瓶座 日期:2013-09-06 12:27:30摩羯座 日期:2013-09-28 14:07:46处女座 日期:2013-10-24 14:25:01酉鸡 日期:2014-04-07 11:54:15
4楼 [报告]
发表于 2013-05-18 13:38 |只看该作者
枚举所有组合是N^2, 哈希存储所有元素后查询可以O(1), 那么最终复杂度就是N^2
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
井蛙夏虫

论坛徽章:
4
白羊座 日期:2013-09-17 21:59:30技术图书徽章 日期:2013-10-12 22:16:03白羊座 日期:2013-10-14 11:01:40双子座 日期:2013-12-17 18:26:39
5楼 [报告]
发表于 2013-05-18 14:35 |只看该作者
回复 3# chinesefys
忘了表格查找可以做到O(1)。


   
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
folklore

论坛徽章:
59
2015年亚洲杯之约旦 日期:2015-01-27 21:27:392015年亚洲杯之日本 日期:2015-02-06 22:09:41拜羊年徽章 日期:2015-03-03 16:15:432015年辞旧岁徽章 日期:2015-03-03 16:54:152015年迎新春徽章 日期:2015-03-04 09:50:282015元宵节徽章 日期:2015-03-06 15:50:392015年亚洲杯之阿联酋 日期:2015-03-19 17:39:302015年亚洲杯之中国 日期:2015-03-23 18:52:23巳蛇 日期:2014-12-14 22:44:03双子座 日期:2014-12-10 21:39:16处女座 日期:2014-12-02 08:03:17天蝎座 日期:2014-07-21 19:08:47
6楼 [报告]
发表于 2013-05-18 18:28 |只看该作者
C. n^3
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
chinesefys

论坛徽章:
0
7楼 [报告]
发表于 2013-05-18 22:25 |只看该作者
回复 6# folklore


    不是最优吧？
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
方兆国

论坛徽章:
19
CU大牛徽章 日期:2013-03-13 15:32:35CU大牛徽章 日期:2013-09-18 15:15:15CU大牛徽章 日期:2013-05-20 10:46:44CU大牛徽章 日期:2013-05-20 10:46:38CU大牛徽章 日期:2013-05-20 10:46:31CU大牛徽章 日期:2013-05-20 10:46:25CU大牛徽章 日期:2013-05-20 10:46:18CU大牛徽章 日期:2013-04-17 11:19:51CU大牛徽章 日期:2013-04-17 11:19:42CU大牛徽章 日期:2013-04-17 11:19:37CU大牛徽章 日期:2013-04-17 11:19:32CU大牛徽章 日期:2013-04-17 11:19:28
8楼 [报告]
发表于 2013-05-18 23:26 |只看该作者
我顶B. O(n^2*logn)
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
chinesefys

论坛徽章:
0
9楼 [报告]
发表于 2013-05-19 19:42 |只看该作者
回复 8# 方兆国


算法是啥样的？

   
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
方兆国

论坛徽章:
19
CU大牛徽章 日期:2013-03-13 15:32:35CU大牛徽章 日期:2013-09-18 15:15:15CU大牛徽章 日期:2013-05-20 10:46:44CU大牛徽章 日期:2013-05-20 10:46:38CU大牛徽章 日期:2013-05-20 10:46:31CU大牛徽章 日期:2013-05-20 10:46:25CU大牛徽章 日期:2013-05-20 10:46:18CU大牛徽章 日期:2013-04-17 11:19:51CU大牛徽章 日期:2013-04-17 11:19:42CU大牛徽章 日期:2013-04-17 11:19:37CU大牛徽章 日期:2013-04-17 11:19:32CU大牛徽章 日期:2013-04-17 11:19:28
10楼 [报告]
发表于 2013-05-19 21:50 |只看该作者
chinesefys 发表于 2013-05-19 19:42
回复 8# 方兆国



时间复杂度最小值的情况是所有数据按序排列，那么查找速率必然介于n^2与n^3之间
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
12下一页
返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号：11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们：huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP