如何优化加油站问题O(n)算法的时间复杂度？附分支语句性能疑问

我是数据结构与算法入门学习者，本次并非寻求问题的正确代码，而是希望了解合适的解决思路，以学习不同场景下数据结构的选用。

针对LeetCode中等难度题目「加油站」，我编写的解法代码如下：

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]):
        startingStation = 0
        didCircuit = -1
        tank = 0
        i = 0
        while i <= len(gas):
            if startingStation == len(gas):
                return -1
            if startingStation == i:
                didCircuit += 1
            if didCircuit == 1:
                return startingStation
            tank += gas[i] - cost[i]
            if tank >= 0:
                i += 1
            if i == len(gas):
                i = 0
            if tank < 0:
                didCircuit = -1
                startingStation += 1
                i = startingStation
                tank = 0

我的疑问：

1. 我认为当前算法的时间复杂度为O(n)，但该代码在处理测试用例时速度过慢。想请教：若当前算法为O(n)，有什么方法可将其时间复杂度优化至O(logn)或进一步提升运行速度？
2. 我知道过多if语句代码不够优雅，但如果每个分支操作都是O(1)，在高迭代次数下，if语句的数量是否会影响函数性能？

解答 #

一、时间复杂度优化与运行速度提升 #

首先明确：「加油站」问题的最优时间复杂度就是O(n)，无法优化到O(logn)。因为问题本质是要验证线性的路径连续性，不存在可以分治或二分的独立子问题，所以logn级别的算法不适用。

你的代码之所以看起来是O(n)但运行慢，核心原因是实际最坏时间复杂度是O(n²)：当每次尝试的起点都无法完成回路时，你会将起点后移1位，然后重新从新起点开始遍历。比如极端测试用例（gas全为1，cost全为2），每次起点都要遍历到当前起点之后的所有站点才会失败，总操作次数是n+(n-1)+...+1 = O(n²)，这才是导致速度慢的根本原因。

正确的O(n)贪心思路如下：

• 先计算所有站点的gas[i] - cost[i]总和，如果总和小于0，直接返回-1（总油量不足以支撑全程）。
• 遍历站点，维护当前油箱剩余油量current_tank和起点start：
  • 每到一个站点，将gas[i]-cost[i]加到current_tank。
  • 如果current_tank < 0，说明从start到当前站点的所有位置都不能作为起点（因为从这些点出发都会在中途油量耗尽），直接将start设为i+1，并重置current_tank为0。
• 遍历结束后，若总油量≥0，返回start即可（题目保证唯一解）。

这种方法只需要遍历一次数组，真正实现O(n)时间复杂度，运行速度会大幅提升。

二、if语句对性能的影响 #

现代CPU具备分支预测功能，所以if语句的性能影响分两种情况：

• 如果分支的跳转是可预测的（比如大部分情况下都走同一个分支，或者跳转规律固定），分支预测的准确率很高，此时if语句的数量对性能影响极小。
• 如果分支的跳转是不可预测的（比如随机出现true/false），分支预测会频繁失败，导致CPU流水线清空、重新加载，这时候即使每个分支是O(1)操作，也会显著降低性能，且if数量越多，影响可能越大。

你的代码中多个独立的if可以合并优化，比如将i += 1后判断i == len(gas)的逻辑合并，减少分支数量，同时让代码逻辑更清晰，也能降低分支预测的压力。例如：

if tank >= 0:
    i += 1
    if i == len(gas):
        i = 0

这样合并后，分支数量减少，逻辑更连贯，也能间接提升性能。

内容的提问来源于stack exchange，提问作者genus20