algorithm - 汽车加油问题(贪心算法)，复杂度为 O(n) 的嵌套 while 循环

Question

输入

(1) the maximum distance that a car can travel with a full tank: L km;

(2) an integer array, [0, x1, x2, …, xn, xn+1], each integer represents the distance between a location and a source point A. The first integer is 0, which is the distance between A and A. The second distance x1, represents the distance between the first gas station and A. There are n gas stations between A and B (the destination). xn is the distance between the last gas station and A, and xn+1 is the distance between B and A.

(3) n, which is the number of gas stations.

输出

The minimum number of refills to get from A to B

代码

numRefills = 0
currentPosition = 0

while(currentPosition <= n){
    lastPosition = currentPosition

    while(currentPosition <= n  &&  x[currentPosition + 1] – x[lastPosition] <= L) {
    currentPosition++;
    }

    if (currentPosition == lastPosition) return IMPOSSIBLE; 
    if (currentPosition <= n) numRefills ++;
}

return numRefills

我的疑问是:

1. Why is the time-complexity of the above code is O(n)? shouldn't it be O(n^2) at least because of nested while loops?
2. How to prove that "Refilling at farthest reachable gas" is a safe move?
3. Are there any alternatives to writing the same code but using for loop?

(简而言之，我理解逻辑但无法计算)

非常感谢任何资源/帮助/提示/指导!

Answer 1

疑问1:

时间复杂度是根据执行的操作数计算的。不管里面有多少嵌套循环...

您的第一个 while 循环执行到 currentPosition <= n嵌套 while 循环执行到 currentPosition <= n && x[currentPosition + 1] – x[lastPosition] <= L .. 在这个循环中你增加了currentPostion .所以你的总操作不可能超过 n次。

例子:

array[0, 10, 20, 30]和 L = 50 ..

对于这种情况，您的第一个 while 循环对于第一步为真。您嵌套了 4 个步骤的循环。然后在第 2 步你的第一个 while 循环 false...所以执行了 N 步...

这就是为什么你的代码很复杂:O ( N ) ...

疑问2:

为了尽量减少加油，您需要使用当前燃料尽可能地走远。如果您越过 k使用当前燃料的加油站，则无需在 1 to k-1 加油车站..在您需要检查的每个车站，是否可以使用当前燃料去下一站。如果你可以用当前的燃料从当前站到下一站，那么当前站的加油箱是多余的。

疑点3:

解决问题的方法有很多种...这是另一种方法:

numRefills = 0
currentPosition = 0
currentFuel = L
while(currentPosition <= n){
   if (currentFuel <= x[currentPosition+1] - x[currentPosition]) {
      currentFuel = L;
      numRefills++;
   }
   currentFuel -= (x[currentPosition+1] - x[currentPostion]);
   if ( currentFuel < 0 ) 
      return Impossible;
   currentPosition++;
}

return numRefills