एक सबसे लंबे पथ एल्गोरिदम की कम्प्यूटेशनल जटिलता एक रिकर्सिव विधि

Question

मैंने ग्राफ़ में सबसे लंबा पथ निर्धारित करने के लिए एक कोड सेगमेंट लिखा था। कोड निम्नलिखित है। लेकिन मुझे नहीं पता कि मध्य में रिकर्सिव विधि के कारण इसमें कम्प्यूटेशनल जटिलता कैसे प्राप्त की जाए। चूंकि सबसे लंबा रास्ता ढूंढना एक एनपी पूर्ण समस्या है, मुझे लगता है कि यह O(n!) या O(2^n) जैसा कुछ है, लेकिन मैं वास्तव में इसे कैसे निर्धारित कर सकता हूं? जहां n नोड्स की संख्या को दर्शाता है और m विज़िट नहीं किए गए नोड्स की संख्या को दर्शाता है (क्योंकि आप longestPathm बार कहते हैं, और वहाँ एक पाश जो दौरा किया परीक्षण 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); 
} 

Answer 1

आपका आवर्तन संबंध, T(n, m) = mT(n, m-1) + O(n) है। आधार मामला T(n, 0) = O(n) है (बस देखे गए परीक्षण)।

इसे हल करें और मेरा मानना ​​है कि आपको टी (एन, एन) ओ (एन * एन!) है।

संपादित

कार्य:

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