Вычислительная сложность алгоритма самого длинного пути с рекурсивным методом - PullRequest
Новая
       14

Вычислительная сложность алгоритма самого длинного пути с рекурсивным методом

5 голосов
/ 14 декабря 2010

Я написал сегмент кода, чтобы определить самый длинный путь в графе.Ниже приведен код.Но я не знаю, как получить вычислительную сложность в этом из-за рекурсивного метода в середине.Поскольку поиск самого длинного пути - это полная проблема NP, я предполагаю, что это что-то вроде O(n!) или O(2^n), но как я могу на самом деле определить его? 

public static int longestPath(int A) {
    int k;
    int dist2=0;
    int max=0;

    visited[A] = true;

    for (k = 1; k <= V; ++k) {
        if(!visited[k]){
            dist2= length[A][k]+longestPath(k);
            if(dist2>max){
                max=dist2;
            }
        }
    }
    visited[A]=false;
    return(max);
}

1 Ответ

8 голосов
/ 14 декабря 2010

Ваше рекуррентное отношение равно T(n, m) = mT(n, m-1) + O(n), где n обозначает количество узлов, а m обозначает количество не посещенных узлов (потому что вы вызываете longestPath m раз, и существует цикл, который выполняет посещенный тест n раз). Базовый случай T(n, 0) = O(n) (только посещенный тест).

Решите это, и я верю, что вы получите T (n, n) = O (n * n!).

EDIT

Рабочая: 

T(n, n) = nT(n, n-1) + O(n) 
        = n((n-1)T(n, n-2) + O(n)) + O(n) = ...
        = n(n-1)...1T(n, 0) + O(n)(1 + n + n(n-1) + ... + n(n-1)...2)
        = O(n)(1 + n + n(n-1) + ... + n!)
        = O(n)O(n!) (see http://oeis.org/A000522)
        = O(n*n!)
...