Java 针对大输入优化算术和赋值运算符

Question

我有一段代码必须在时钟速度方面运行得非常快。该算法已经在 O(N) 中。需要2秒，需要1秒。对于大多数 A.length 输入 ~ 100,000，它需要 0.3 秒，除非特定代码行被调用了极端次数。 (对于深奥的编程挑战)

它使用算术级数的计算 1,2,..N -> 1,3,4,10,15.. 可以表示为 n*(n+1)/2 我循环遍历这个等式数十万次。 我无权访问输入，也无法显示它。我能够返回的唯一信息是运行时间。 特别是等式是:

s+=(n+c)-((n*(n+1))/2);

s 和 c 的取值范围为 0 到 10 亿

n 的范围是 0 到 100,000

就时钟速度而言，编写此语句的最有效方法是什么？ 我听说除法比乘法需要更多的时间，但除此之外，我无法确定是在一行中还是在多个赋值行中编写更有效率。 先除后乘还是先乘后除？ 创建自定义整数类型也会有很大帮助吗？

根据要求进行编辑，输入小写的完整代码(对不起，如果它很难看，我只是不断地剥离它):

public static void main(String[] args) {

        int A[]={3,4,8,5,1,4,6,8,7,2,2,4};//output 44
        int K=6;
        //long start = System.currentTimeMillis();;
        //for(int i=0;i<100000;i++){
            System.out.println(mezmeriz4r(A,K));
        //}
        //long end = System.currentTimeMillis();;

//      System.out.println((end - start) + " ms");

    }
    public static int mezmeriz4r(int[]A,int K){
        int s=0;
        int ml=s;
        int mxl=s;
        int sz=1;
        int t=s;
        int c=sz;
        int lol=50000;
        int end=A.length;
        for(int i=sz;i<end;i++){
            if(A[i]>A[mxl]){
                mxl=i;
            }else if(A[i]<A[ml]){
                ml=i;
            }
            if(Math.abs(A[ml]-A[mxl])<=K){
                sz++;
                if(sz>=lol)return 1000000000;
                if(sz>1){
                    c+=sz;
                }
            }else{
                if(A[ml]!=A[i]){
                    t=i-ml;
                    s+=(t+c)-((t*(t+1))/(short)2);
                    i=ml;
                    ml++;
                    mxl=ml;
                }else{
                    t=i-mxl;
                    s+=(t+c)-((t*(t+1))/(short)2);
                    i=mxl;
                    mxl++;
                    ml=mxl;
                }
                c=1;
                sz=0;
            }
        }
        if(s>1000000000)return 1000000000;
        return s+c;
    }

---

挑战归来:

检测到的时间复杂度:

O(N)

测试时间结果

例子 示例测试 0.290 秒。好的

单例 单个元素 0.290 秒。好的

双 两个元素 0.290 秒。好的

小功能 小型功能测试 0.280 秒。好的

小随机 小随机序列长度 = ~100 0.300 s。好的

small_random2 小随机序列长度 = ~100 0.300 s。好的

中等_随机 混沌介质序列长度 = ~3,000 0.290 s。好的

大范围 大范围测试，长度 = ~100,000 2.200 s。超时错误 运行时间:>2.20 秒，时限:1.02 秒。

大随机 随机大序列长度 = ~100,000 0.310 s。好的

大答案 用大答案 0.320 s 进行测试。好的

大到极 所有最大值 = ~100,000 0.340 s。好的

Answer 1

通过一点代数，您可以将表达式 (n+c)-((n*(n+1))/2) 简单地转换为 c-((n*( n-1))/2) 删除加法运算。然后，您可以用 1 向右移位来替换 2 的除法，这比除法更快。尝试更换

s+=(n+c)-((n*(n+1))/2);

与

s+=c-((n*(n-1))>>1);