提高代码性能

Question

今天我听说这个名为codility的网站,用户可以通过各种编程测试来检查代码的性能.

当我开始时,他们向我展示了这个样本测试,

任务描述一只小青蛙想要到达路的另一边.青蛙目前位于X位置并且想要到达大于或等于Y的位置.小青蛙总是跳跃固定的距离,D.计算小青蛙必须达到目标的最小跳跃次数.

写一个函数: class Solution { public int solution(int X, int Y, int D); } 给定三个整数X,Y并D返回从位置X到等于或大于的位置的最小跳跃次数Y.

例如,给定:
X = 10
Y = 85
D = 30函数应该返回3,因为青蛙将按如下方式定位:

在第一次跳跃之后,位置10 + 30 = 40

第二次跳跃后,位置10 + 30 + 30 = 70

在第三次跳跃后,位置10 + 30 + 30 + 30 = 100

假设:X,Y和D是该范围内的整数

[1..1,000,000,000]; X≤Y.复杂性:预计最坏情况时间

复杂度是O(1); 预期的最坏情况空间复杂度为O(1).

问题非常简单,我花了2分钟时间编写解决方案,这是以下内容,

class Solution {
    public int solution(int X, int Y, int D) {

        int p = 0;
        while (X < Y){
            p++;
            X = X + D;
        }
    return p;
    }
}

但是,测试结果显示我的代码的性能只是20%和我得分55%,

以下是结果链接,https://codility.com/demo/results/demo66WP2H-K25/

这是如此简单的代码,我刚刚使用了一个while循环,它怎么可能更快？

Answer 1

基础数学:

X + nD >= Y
nD >= Y - X
n >= (Y - X) / D

n的最小值将是(Y - X)除以D的结果.

此操作的大O分析:

• 复杂性:O(1).这是一个区别,分裂和整理
• 最坏情况的空间复杂度为O(1):您最多可以有3个变量:
  • Y - X的差异,我们将其分配给Z.
  • 在Z之间划分D,让我们将其分配到E.
  • 舍入E,让我们将其分配到R(从结果).

Answer 2

Java（一行），正确性100%，性能100%，任务得分100%

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int X, int Y, int D) {
      return (int) Math.ceil((double) (Y - X) / (double) D);
    }
}