Zeitkomplexitätsanalyse für nicht-ovarlappendes Teilproblem Rekursive Lösung

-3

Hier lege ich nur Python-Code.Zeitkomplexitätsanalyse für nicht-ovarlappendes Teilproblem Rekursive Lösung

Rec(Arr,N,K,X) : 
    if(X==0 and K==0): 
     return 1 
    elif(X<=0 or K<=0 or N<0): 
     return 0 
    else : 
     return Rec(Arr,N-1,K,X)+Rec(Arr,N,K-1,X-Arr[N])

Vorausgesetzt, dass alle Elemente von Ank verschieden sind, schließt dies, dass alle Teilprobleme nicht überlappende sind (nur einen kleinen Koffer nahm, tun Sie es manuell)

Bitte Bewerten Zeit Komplexität in Bezug auf N, K, X. Danke für das Lesen dieser Frage ...

Quelle

2016-05-12 Ramesh Chandra

Was ist falsch mit meiner Queue..alles wird einfach abgelehnt..kann irgendjemand auf das Problem hinweisen? –

Mit welcher Komplexität sind Sie angekommen? Und warum denkst du, dass es falsch ist? –

@ cristiano-sousa Ich dachte, als O (N * K) .. Ich weiß, das ist falsch, weil ich TLE vorausgesetzt, dass N <= 50 && K <= 10. DANK # Takoika..Aber ich habe seine Lösung nicht verstanden..aber es gab mir einen Hinweis, dass diese Lösung nicht funktionieren wird, musste ich für mehr optimierte Lösung suchen –

Grundsätzlich wird dieses Problem als Tiefensuche eines Binärbaums betrachtet, dessen Höhe von max(N,K) begrenzt wird. Die Reihenfolge der zeitlichen Komplexität wird durch begrenzt. Und dann X und Arr könnte diese Zeit Komplexität reduzieren. Aber es ist unklar, weil es von den Werten Arr und X abhängt. (Wenn z. B. Arr = [inf, ..., inf] ist, wird die Zeitkomplexität N sein.)

Quelle

2016-05-12 10:56:13 takoika

Könnten Sie bitte etwas mehr erklären? –

Angenommen, X es nie verlassen .. Worst Case..als –

2^max (N, K) ist Obergrenze ohne X und Arr. – takoika

Zeitkomplexitätsanalyse für nicht-ovarlappendes Teilproblem Rekursive Lösung

Antwort

Verwandte Themen