Когда вы делаете a[i] = a[j] + a[i], вы на самом деле просто делаете a[i]++, так как a[j]==1 каждый раз запускаете эту строку. Если это не очевидно сразу, вам следует вручную проследить выполнение вашего кода и посмотреть, что он на самом деле делает.
Что вы, вероятно, хотели:
for j in range(n):
for i in range(j):
if x[i] < x[j]:
a[j] += a[i]
Рекуррентное соотношение: количество возрастающих подпоследовательностей, заканчивающихся на j, равно сумме числа возрастающих подпоследовательностей, заканчивающихся на каждый индекс меньше j, плюс 1 для последовательности, содержащей только j.
Анализ
Это решение O (n ^ 2). Доказательство: первая итерация внешнего цикла, мы повторяем 1 раз во внутреннем цикле (внутренний цикл выполняет постоянное количество вычислений на каждой итерации). Каждый раз, когда мы увеличиваем j, мы увеличиваем количество итераций во внутреннем цикле. В итоге мы вызываем код внутри внутреннего цикла всего 1 + 2 + 3 + ... (n-1) + n раз. Пусть f(n) = 1 + 2 + 3 + ... n.
Вспомним определение слова big-O: f(n) = O(n^ 2) означает, что существуют положительные константы c и k, такие что 0 ≤ f(n) ≤ cn^2 для всех n ≥ k. Значения c и k должны быть фиксированными для функции f и не должны зависеть от n.
Ясно 0 ≤ f(n), поэтому нам просто нужно показать, что существуют некоторые c и k такие, что f(n) ≤ cn^2 для всех n ≥ k. Я выберу c=1 и k=1. Вы можете убедиться, что f(n) <= n^2 для всех n.
Хотя вы не спрашивали, ваш комментарий ниже говорит о том, что вам нужно доказательство того, что это самая жесткая граница, которую мы можем получить. Так что я докажу, что f(n) = Ω(n^2)
f(n)=Ω(n^2) если для некоторой константы c>0 и всех достаточно больших n, то f(n) ≥ cn^2.
Давайте выберем c=4. Затем у нас есть f(n) = 1 + 2 + 3 + ... n >= (n/2) + (n/2)+1 + (n/2)+2 + ... n, где мы просто вычли 1 + 2 + ... (n/2)-1 из f(n), чтобы получить это неравенство.
Кроме того, (n/2) + (n/2)+1 + (n/2)+2 + ... n >= (n/2)*(n/2), так как мы можем взять все n/2 условия, равные >= n/2, и ограничить их ровно на n/2 каждый.
Но (n/2)*(n/2) = (n^2)/4, поэтому у нас есть f(n) >= (1/4)n^2 для всех n, поэтому мы показали, что f(n) = Ω(n^2).
03.07.2015
if(dp[x]) return dp[x]— это то, что препятствует тому, чтобы это выполнялось в экспоненциальное время, пересчитывая DP(i) каждый раз, когда нам это нужно для вычисленияDP(i+1),DP(i+2)и т. д. Эта строка говорит, что если мы уже вычислилиdp[x], просто найдите его в таблице и верните. . Кроме того, это выполняется за O(n^2), так как для каждогоxнам нужно суммировать значения для каждогоi<x. 03.07.2015