Наибольшее увеличение подпоследовательности с O (N^2) с использованием рекурсии

Question

LIS: Самая длинная увеличивающаяся проблема подпоследовательность найти подпоследовательность заданной последовательности, в которой элементы подпоследовательности находятся в отсортированном порядке, самого низкого до самого высокого

Eg:

0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15

самую длинную возрастающую подпоследовательность равно 0, 2, 6, 9, 13, 15.

Я могу разработать LIS различными способами, такими как методы динамического программирования и запоминания, но с конкретным случаем, когда мне нравится реализовать LIS с использованием рекурсии со сложностью времени O(N^2).

С Я думаю, с помощью рекурсии мы не можем реализовать алгоритмы с временной сложностью O(N^2). (Пожалуйста, поправьте меня)

Однако я получил этот алгоритм от Google

Algorithm LIS(A,n,x) 
1: if n = 0 then 
2: return 0 
3: m LIS(A; n -1; x) 
4: if A[n] < x then 
5: m =max(m; 1 + LIS(A; n-1;A[n])) 
6: print(m) 

Является ли этот алгоритм O(N^2)?

Не могли бы вы объяснить?

Answer 1

Этот алгоритм печатает максимум в массиве Первый аргумент (A) - это массив, второй аргумент (n) - это индекс элемента, который теперь проверяет max и третий аргумент (x), является максимальным за это время. В худшем случае у вас есть отсортированный массив и в каждой проверке (если A [n] < x then), вам нужно обновить третье аргумент max, что означает, что вам нужно проверить весь массив.

алгоритм принимает максимум от индекса n до n-1 и проверяет, что с max от n до n-2 и проверьте, что с max от n до n-3, и он продолжает проверять с n на 1, чтобы получить макс.

, что означает, что он представляет собой О (п + (п-1) + (N-2) + ... + 2 + 1) = O (N^2)

К сожалению о Pic Качество :)