假设有一组值(大于等于0的数),总量级别:百万以上,需要求出总和在某个值(Y)的位置。实际情况中Y的值一般也是上万的。
比如:有 5,2,0,3,4,6,7,1,11,3 等求在Y=12的位置,
分析如下:
值: 5,2,0,3, 4, 6, 7, 1,11,3
累计:5,7,7,10,14,20,27,28,39,41
此时临界点在第4个数【3】那。如果是10的话,位置也是第4个数。
数据在数据库中,实际处理不考虑数据的排序问题,只需要从总量中找到一片数据总量接近或等于Y。
已知道的算法,
1,逐条累计,可能需要较长时间
2,先按大到小排序,逐块累计,比上面快些。(操作是允许排序的)
3,类似2分的算法,直接对半,累加前半数据比较,大的话再减少一半,小的话加上剩余的一半。无限2分,直至累计值与Y的接近或等于。
这个算累计 我是在数据库ORACLE中做的。
1、原始表:
t_bill;字段:索引ID(number),分钟值talktime(varchar(40));
2、递归累加生成表:
t_bill_2 ;字段:索引ID(number),分钟值talktime(varchar(40));
递归累加生成表 talktime建立索引
两个表的id一样;
3、可以考虑根据递归累加生成表的talktime分表; 比如1--1000的在1表,依次类推;
4、根据根据Y值查分表编号,然后查
两个数比较比加运算要省时间,尽量减少加的运算次数,已知Y的值,那么也就是说必须一个一个计算累加到Y附近,这个运算至少要进行一次,则1和2的方法比3要快,最好是从大到小排序,这么的话尽量少的加运算就可以累加到Y值。
假设有一组值(大于等于0的数),总量级别:百万以上,需要求出总和在某个值(Y)的位置。实际情况中Y的值一般也是上万的
1.
(1000000个数的和) / 1000000 = 一百万的数的平均值
2.
Y / 一百万的数的平均值=等于大约需要累加多少数,然后以这个位置开始判断
3
相差值不大的话就慢慢比较,比较大的话,就从这个位置开始,按步骤1,继续
1.(1000000个数的和) / Y = 以这个数为步长
2 每次按这些这个步长 把数加起来和Y比较
相差不大就一个个慢慢比较 相差大的话 跳转到1 ,按1方法比较。
这个问题的任何方法都只能是O(N)
但是我说的方法二能比较快的接近。
jinnianshilongnian
第三方用到数据库.....,这个。。。呵呵