Algorithm筆記 7 - 最少加油次數演算法分析

承筆記6，我們嘗試來寫此問題的解決演算法。

這個演算法接受三個參數：

x是一個array，包含從出發點A, 終點B, 和所有加油站的位置：

n是個加油站的array index
L是加滿油可以跑得最大距離

所以演算法寫起來相當簡單：

不過這是一個O(n^2)的演算法，因為有nested loop，而內外loop各是跑最多n次。

藉由不同implementation的方式，我們可以將之變成O(n)的演算法：

public static int minRefills(int[] positions, 
                             int secondLastGasStationIndex, 
                             int farestDistanceCanGo) {
    int numRefills = 0;
    int currentPosition = 0;
    int lastRefill = currentPosition;

    while (currentPosition <= secondLastGasStationIndex) {

        if (positions[currentPosition + 1] - positions[lastRefill] <= farestDistanceCanGo )
            currentPosition += 1;
        else {
            lastRefill = currentPosition;
            numRefills += 1;
        }

    }

    return numRefills;
}

以上的演算法沒驗證過，但大概就是這樣。

這邊的教訓是implementation optimization是很有影響（廢話一句）。