给定一个整数sum，从有N个无序元素的数组中寻找元素a、b、c、d，使得 a+b+c+d =sum，最快的平均时间复杂度是____。

阅读量：2386 次

发布时间：2019-05-10

本文共 378 字，大约阅读时间需要 1 分钟。

给定一个整数sum，从有N个无序元素的数组中寻找元素a、b、c、d，使得 a+b+c+d =sum，最快的平均时间复杂度是____。

正确答案: E 你的答案: C (错误)

O(N^2)

O(log N)

O(N)

O(N^3)

O(N^2LogN)

O(N^4)

O(N^3LogN)的算法：

三重for循环穷举a,b,c的值，剩下d = sum-a-b-c,使用二分查找(数组事先排好序)来确定d是否存在。

O(N^2LogN)的算法：

预先枚举c,d得到c+d的n^2个数字并排好序。

双重for循环穷举a,b的值，再使用二分查找确定c+d是否存在。

c+d的值得出来后同样枚举得出c,d的值。（或者在第一步就浪费一些空间将c+d对应的c,d存好，此时直接取出即可。)

排序及循环二分查找都为O(n^2logn)时间，总的O(n^2logn)时间。

转载地址：http://nziab.baihongyu.com/

你可能感兴趣的文章

通过修改kong属性解决不能获取外网域名的问题

yii框架在layout模式下，模版和layout文件的渲染顺序

查看>>

php5对象复制、clone、浅复制与深复制

查看>>

php设计模式

查看>>

git与github在ubuntu下的使用

sysbench 0.5 性能测试工具使用手册

查看>>

通过telnet连接查看memcache服务器

查看>>

django不用在数据库中创建新的user表而使用它的后台管理功能

查看>>

php array_unshift()修改数组key

查看>>

mysql性能优化-查询(Query)优化-2

MongoDB与MySQL的插入、查询性能测试

查看>>

深入理解OAuth2.0协议

查看>>

https原理：证书传递、验证和数据加密、解密过程解析

查看>>