Самая большая возрастающая подпоследовательность с O (n ^ 2) с использованием рекурсий

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

Eg:

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

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

Я могу разработать ЛИС, используя различные способы, такие как динамическое программирование и методы запоминания, но в конкретном случае мне нравится реализовывать ЛИС с использованием рекурсии со временной сложностью 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)?

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


java recursion algorithm time-complexity lis
person Krishna Chikkala    schedule 06.11.2014    source источник
comment
Зачем вам O(N^2)? Можно реализовать O(N) рекурсивную адаптацию. Просто заставьте метод возвращать позицию и длину найденной последовательности.   -  person Basilevs    schedule 06.11.2014

Ответы (1)


arrow_upward
1
arrow_downward

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

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

это означает, что это O (n + (n-1) + (n-2) +... + 2 + 1) = O (n ^ 2)

pic

Извините за качество фото :)

person dev-masih    schedule 06.11.2014
comment
Этот алгоритм выводит максимум в массиве. Первый аргумент (A) — это массив. Что вы подразумеваете под этим? позвольте мне быть более конкретным. Этот алгоритм будет генерировать размер наибольшей возрастающей подпоследовательности из случайного набора чисел (A) размера n, и мы используем x, чтобы отслеживать большое число и постоянно обновлять его для каждой рекурсии. извините, если вы ясно с ques. мой второй вопрос: O(nx(n-1)x(n-2)x...x2x1) = O(n^2) здесь вы умножаете каждую итерацию, что дает n! но не сумма первых n натуральных чисел, пожалуйста, не могли бы вы уточнить второй вопрос. Заранее спасибо. - person Krishna Chikkala; 06.11.2014