首页 > 其他 > 详细

【待字闺中】数对数目

时间:2014-09-03 00:10:25      阅读:329      评论:0      收藏:0      [点我收藏+]

题目:

给定两个数组X和Y,元素都是正数。请找出满足一下条件的数对的数目:

1.x^y>y^x,即x的y次方>y的x次方

2.x来自X数组,y来自Y数组

 

分析,

一。暴力搜索。

X数组长度m,Y数组长度n, 复杂度o(m*n)

 

二。数学变换。

log(x)/x>log(y)/y

1.数组X,Y分别代入f(a)=log(a)/a

2.对Y进行排序O(nlogn)

3.遍历X数组,对于每一个x,在Y中,进行二分查找,即可。

所以,总的复杂度为 O(nlogn+mlogn)

 

 

 

 

//注意:排序和二分,复杂度不清楚。

【待字闺中】数对数目

原文:http://www.cnblogs.com/karcylee/p/3952530.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!