汽车加油问题（贪心算法），复杂度为 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

我的疑惑是：

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?

How to prove that "Refilling at farthest reachable gas" is a safe move?

Are there any alternatives to writing the same code but using for loop?

（总之，我理解了逻辑，但我无法计算）

非常感谢resources/help/hint/guidance！

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 )...

疑问二：

为了尽量减少加油，您需要在当前 fuel.If 的情况下走得更远，您使用当前的燃料穿过 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

Answer 2

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n,k;
    cin>>n>>k;
    int arr[k];
    for(int i=0;i<k;i++)
    {
        cin>>arr[i];
    }

    int diff=arr[0],refills=0,fuelCnt=3,flag=1;

    for(int i=0;i<k;i++)
    {
        if(i!=0)
        {
            diff=arr[i]-arr[i-1];
        }



        if(fuelCnt < diff)
        {
            fuelCnt=3;
            refills++;
        }
        fuelCnt-=diff;
        cout<<"fuelCnt is "<<fuelCnt<<"\n";
        if(fuelCnt <0)
        {
            flag=0;
            break;

        }
    }

    //Check if there is enough fuel to reach last stop
    diff=n-arr[k-1];
    fuelCnt-=diff;
    if(fuelCnt <0)
    {
        flag=0;
    }
    if(fuelCnt < diff)
    {
        refills++;
    }

    if(flag!=1)
    {
        cout<<"Imposible"<<"\n";
    }
    else
    {
        cout<<refills<<"\n";
    }

}

check whether code is correct ???

Answer 3

Coursera 在 C++ 中接受这个解决方案

#include <iostream>
#include <vector>
using namespace std;

int compute_min_refills(int dist, int tank, vector<int> &stops){
    stops.push_back(dist);
    int lastStop = 0;
    int numberStop = 0;
    int x = 0;

    for (int i = 0; i < stops.size() - 1; i++)
    {

        if (stops[i] - lastStop <= tank)
        {
            x = stops[i];
            if (stops[i + 1] - lastStop > tank)
            {
                numberStop++;
                lastStop = x;
            }
        }
        if (tank < stops[i] - lastStop)
        {
            //cout << "uzak" << endl;
            return -1;
        }

        //cout << "x :: " << x << "  last stop ::  " << lastStop << " number stop :: " << numberStop << endl;
    }
    if (dist > lastStop + tank)
    {
        return -1;
    }

    return numberStop;
}

int main()
{
    int d = 0;
    cin >> d;
    int m = 0;
    cin >> m;
    int n = 0;
    cin >> n;

    vector<int> stops(n);
    for (size_t i = 0; i < n; ++i)
        cin >> stops.at(i);

    cout << compute_min_refills(d, m, stops) << "\n";

    return 0;
}

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

Car Fueling Problem (Greedy Algorithm), Nested while loop with O(n) complexity

algorithm

while-loop

greedy

疑问1：

疑问二：

疑问3：