O(1) 恒定时间解决方案示例？

Question

我有一个任务需要计算青蛙从位置 X 跳到大于或等于 Y 的位置，给定每次跳跃的固定距离 (D)。

例如 X = 10; Y = 85； D = 30;答案 = ((Y-X)/D) = 3;

解决方案的复杂度必须是 O(1)。

显而易见的解决方案无效：

int diff=Y-X;
int jumps=diff/D;

因为如果跳转 returns 一个向下舍入的双精度数，这将不等于或大于。

我可以使用 while 循环：

int diff=Y-X;
int jumps=0;
int jumps_counter=0;

while(jumps<diff)
{
 jumps+=D;
 jumps_counter++;
}

但是显然这不会是 O(1)，而是 O(x-y)...

解决这个问题的最佳方法是什么？

Answer 1

显而易见的解决方案是将其四舍五入。

int diff = Y-X;
int jumps = std::ceil((double)diff/D);

这是一个复杂度为 O(1) 的操作，避免了循环查找所需的步骤数。

Answer 2

D = 30 尺码跳跃，从 10 开始会给你

10 ---> 40 ---> 70 ---> 100

总共跳了 3 次..

您需要一个简单的公式：ceil((y-x)/d) 其中 ceil(z) 是大于 z 的最小整数

在python中就像

import math
math.ceil( (float)(y-x)/d )

Answer 3

整数运算

int jumps = diff / D + (diff % D ? 1 : 0);

O(1) Constant time solution example?