"Detected time complexity: O(Y-X)" 是什么意思？

Question

我正在做一些 Codility 编码实践，在结果中，我得到了这个 "Detected time complexity: O(Y-X)"。我不明白这到底是什么意思。这是因为我糟糕且不断循环？如何增强或改善性能以摆脱这种糟糕的表现？

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,000,000,000] 范围内。
起点小于或等于终点。

Answer 1

我认为 "Detected time complexity: O(Y-X)" 的意思是说当开始和结束相距较远时，您的代码需要更长的时间才能运行。具体来说，运行您的代码所花费的时间相对于开始和结束之间的差异 线性增加 。请注意，我假设 Y 是结束，X 是开始。

这里实际上不需要循环。您可以做一些数学运算来计算出您需要多少次跳跃，并在恒定时间 O(1) 内执行此操作。

首先，您通过计算开始和结束之间的差来计算您必须跳跃的距离：

int distance = endPoint - startPoint;

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

int jumps = distance / frogJumpPowerDistance;

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

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

编辑：

正如 iakobski 在评论中所建议的，这也可以只用一个除法来完成，如下所示：

return (distance - 1) / frogJumpPowerDistance + 1;

"Detected time complexity: O(Y-X)" 是什么意思？

What does this mean "Detected time complexity: O(Y-X)"?

c#

algorithm

loops

performance-testing

time-complexity