确定算法的时间复杂度

Question

您好，我无法确定该算法的时间复杂度。该算法的作用是找到从一种货币到另一种货币的最大转换。它使用 DFS 和回溯，很明显 space 复杂度是 O(depth) 但时间复杂度让我感到困惑。我不确定它是 O(V*E) 还是 O(V+E) 还是 O(V!)。我将不胜感激任何帮助。谢谢！

def get_currency_exchange_rate(source, target, graph):

    def backtrack(current, seen):
        if current == target:
            return 1

        product = 0
        if current in graph:
            for neighbor in graph[current]:
                if neighbor not in seen:
                    seen.add(neighbor)
                    product = max(product, graph[current][neighbor] * backtrack(neighbor, seen))
                    seen.remove(neighbor)

        return product

    return backtrack(source, {source})




g = {
    "A": {"B": 6, "D": 1},
    "B": {"A": 1/6, "D": 1/2, "E": 3, "C": 5},
    "D": {"A": 1, "B": 2, "E": 1/3},
    "E": {"B": 1/3, "D": 3, "C": 1/5},
    "C": {"B": 1/5, "E": 5}
}
curr1 = "A"
curr2 = "C"
print(get_currency_exchange_rate(curr1, curr2, g))

Answer 1

这确实是 O(V!)，尽管它可能更接近 O((V-2)!)。考虑一个有 n 个顶点的图，每个顶点都连接到所有其他顶点。您的回溯循环将遍历以 'source' 开头的顶点的所有 n-1! 排列，除非它在到达 'target' 节点时停止探索排列。这种提前停止确实减少了 V 的两个因素，但运行时间仍将比指数增长快。

您正在尝试求解 Longest-Path Problem, which in general is NP-hard. However, this (very likely) doesn't matter for your use case with currencies: you can solve this in O(V*E) time using the Bellman-Ford algorithm. 最短路径。

最大货币转换是来自源的任何路径中权重的最大乘积。要将其转换为 'finding the minimum sum of weights'，请取每个权重的对数，然后乘以 -1。此新图中的最短路径将是旧图中的 maximum-product 路径。

为什么这行得通，而 longest-path 通常是 NP-hard？如果图形具有正循环，则由于存在负循环，否定所有权重并找到最短路径将失败（尽管 Bellman-Ford 会告诉您存在负循环）。然而，如果你的转换图有一个负循环，你的原始图形有一个乘积大于 1 的循环。在这种情况下，有一组货币可以让你通过按顺序重复转换它们来产生无限的钱。

如果你的use-case确实允许infinite-money个循环存在，但只允许你转换为每种货币一次，这相当于一般的longest-path问题，所以这个技术不行。

确定算法的时间复杂度

Determining Time Complexity For an Algorithm

python

algorithm

backtracking

time-complexity

depth-first-search