这意味着“检测到的时间复杂度：O（YX）”是什么意思？

Question

我正在执行一些Codility编码实践，结果得到了“检测到的时间复杂度：O（YX）”。我不明白这是什么意思。是因为我糟糕且不断循环吗？如何增强或改善性能以摆脱这种不良性能？

public static int Solution(int startPoint, int endPoint, int frogJumpPowerDistance)
{
            int jumpCount = 0;

            // AIM: return the number of jumps to reach endPoint

            // CHECK: no jump needed.
            if (startPoint == endPoint) return jumpCount;

            int distanceReach = startPoint + frogJumpPowerDistance;
            jumpCount++;
            if (distanceReach < endPoint)
            {
                //enter checking loop
                do
                {
                    distanceReach += frogJumpPowerDistance;
                    jumpCount++;
                }
                while (distanceReach < endPoint);
            }

            return jumpCount;
}

我希望不会收到超时错误。但是我明白了。

我不确定如何改善代码以解决超时错误。

对于输入（5，1000000000，2），解决方案超出了时间限制。

供你参考，

1. 所有输入都在[1 ... 1,000,000,000]范围内。

2. startPoint小于或等于endPoint。

Answer 1

我认为“检测到的时间复杂度：O（YX）”的意思是，当起点和终点相距较远时，您的代码将花费更长的运行时间。具体来说，相对于开始和结束之间的差异，运行代码所需的时间呈线性增加。请注意，我假设这Y是结束，X而是开始。

您实际上不需要在这里循环。您可以做一些数学运算来找出所需的跳数，并在恒定时间O（1）中进行。

首先，通过计算起点和终点之间的差来计算必须跳过的距离：

int distance = endPoint - startPoint;

然后，将距离除以跳跃力：

int jumps = distance / frogJumpPowerDistance;

如果distance能被整除frogJumpPowerDistance，那么我们就可以返回jumps。否则，在我们跳了jumps几次之后，我们还有一段距离（这是整数除法！）。因此，我们需要再跳一次才能完成。

if (distance % frogJumpPowerDistance == 0) {
   return jumps;
} else {
   return jumps + 1;
}

编辑：

正如iakobski在评论中建议的那样，也可以只划分一个部分，例如：

return (distance - 1) / frogJumpPowerDistance + 1;