Determining Time Complexity For an Algorithm-CodePudding

Hi I am having trouble determing the time complexity for this algorithm. What the algorithm does is it finds the maximum conversion from one currency to another. It uses DFS and Backtracking and it is clear that the space complexity is O(depth) but the time complexity is confusing me. I am not sure if it is O(V*E) or O(V E) or O(V!). I would appreciate any help. Thanks!

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

CodePudding user response：

This is indeed O(V!), although it's probably closer to O((V-2)!). Consider a graph with n vertices, with each vertex connected to all other vertices. Your backtracking loop will go through all n-1! permutations of vertices that start with 'source', except it will stop exploring a permutation when it reaches the 'target' node. This early stopping does shave off two factors of V, but runtime will still grow faster than exponentially.

You're trying to solve the 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. for shortest paths.

The maximum currency conversion is the maximum product of weights in any path from source. To convert this into 'finding the minimum sum of weights', take the logarithm of each weight, and multiply it by -1. The shortest path in this new graph will be the maximum-product path in your old graph.

Why does this work, when longest-path is usually NP-hard? If a graph has positive cycles, negating all of the weights and finding shortest paths will fail due to the presence of negative cycles (although Bellman-Ford will tell you a negative cycle exists). However, if your converted graph has a negative cycle, your original graph had a cycle whose product is greater than 1. In that case, there is a set of currencies which will allow you to generate infinite money by repeatedly converting them in order.

If your use-case does allow for infinite-money cycles to exist, but only allows you to convert to each currency once, this is equivalent to the general longest-path problem, so this technique will not work.