Zeitkomplexität der dynamischen Programmierung ⇐ Python

[Anonymous]

Ich schaue mir eine der Lösungen für das Programmierungsproblem an: Partition A in zwei Untergruppen gleicher Summe einstellen. Das Programmierungsproblem: Bei einem Array arr [] ist die Aufgabe zu prüfen, ob sie in zwei Teile partitioniert werden kann, so dass die Summe der Elemente in beiden Teilen gleich ist. Ich habe die zeitliche Komplexität der Lösung berechnet, die als "[besserer Ansatz 1] unter Verwendung von Top-Down-DP (Memoisierung)" bezeichnet wird, der den folgenden Code hat: < /p>
# Python program to partition a Set
# into Two Subsets of Equal Sum
# using top down approach
def isSubsetSum(n, arr, sum, memo):

# base cases
if sum == 0:
return True
if n == 0:
return False

if memo[n-1][sum] != -1:
return memo[n-1][sum]

# If element is greater than sum, then ignore it
if arr[n-1] > sum:
return isSubsetSum(n-1, arr, sum, memo)

# Check if sum can be obtained by any of the following
# (a) including the current element
# (b) excluding the current element
memo[n-1][sum] = isSubsetSum(n-1, arr, sum, memo) or\
isSubsetSum(n-1, arr, sum - arr[n-1], memo)
return memo[n-1][sum]

def equalPartition(arr):

# Calculate sum of the elements in array
arrSum = sum(arr)

# If sum is odd, there cannot be two
# subsets with equal sum
if arrSum % 2 != 0:
return False

memo = [[-1 for _ in range(arrSum+1)] for _ in range(len(arr))]

# Find if there is subset with sum equal
# to half of total sum
return isSubsetSum(len(arr), arr, arrSum // 2, memo)

if __name__ == "__main__":
arr = [1, 5, 11, 5]
if equalPartition(arr):
print("True")
else:
print("False")
< /code>
Die Website besagt, dass die zeitliche Komplexität des obigen Code O (N * Sum) ist, aber ich dachte, dass es o (2 ^ n) wegen der Zeile < /p>
sein muss memo[n-1][sum] = isSubsetSum(n-1, arr, sum, memo) or\
isSubsetSum(n-1, arr, sum - arr[n-1], memo)
< /code>
Warum ist die Zeitkomplexität o (n * sum) anstelle von o (2 ^ n)? Ich bin ziemlich neu in der Berechnung der Zeitkomplexität aus einem Programmiercode.