weixin_42501429
2012-08-30 09:17 阅读 301
已采纳

一个临界点的问题

假设有一组值(大于等于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中做的。

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享

4条回答 默认 最新

  • 已采纳
    jinnianshilongnian jinnianshilongnian 2012-08-30 12:54

    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值查分表编号,然后查

    点赞 评论 复制链接分享
  • zyn010101 zyn010101 2012-08-30 09:30

    两个数比较比加运算要省时间,尽量减少加的运算次数,已知Y的值,那么也就是说必须一个一个计算累加到Y附近,这个运算至少要进行一次,则1和2的方法比3要快,最好是从大到小排序,这么的话尽量少的加运算就可以累加到Y值。

    点赞 评论 复制链接分享
  • cttnbcj ccccj 2012-08-30 14:51

    假设有一组值(大于等于0的数),总量级别:百万以上,需要求出总和在某个值(Y)的位置。实际情况中Y的值一般也是上万的
    1.
    (1000000个数的和) / 1000000 = 一百万的数的平均值
    2.
    Y / 一百万的数的平均值=等于大约需要累加多少数,然后以这个位置开始判断
    3
    相差值不大的话就慢慢比较,比较大的话,就从这个位置开始,按步骤1,继续

    点赞 评论 复制链接分享
  • cttnbcj ccccj 2012-08-30 17:42

    1.(1000000个数的和) / Y = 以这个数为步长
    2 每次按这些这个步长 把数加起来和Y比较
    相差不大就一个个慢慢比较 相差大的话 跳转到1 ,按1方法比较。

    这个问题的任何方法都只能是O(N)
    但是我说的方法二能比较快的接近。

    jinnianshilongnian
    第三方用到数据库.....,这个。。。呵呵

    点赞 评论 复制链接分享

相关推荐