Наибольшее возрастающее подпоследовательность линейное время

-1

Я читал самую длинную возрастающую проблему подпоследовательности: Приведенный массив A = {a_1, a_2, ..., a_n}, нашел длину самой длинной возрастающей подпоследовательности (не обязательно смежной) Я думал рекурсивного решения, которое с memoization (или DP) имеет сложность = O (n * max (a_i)). поэтому в основном n * диапазон a_i. Все найденные решения: O (n^2) или O (nlogn), что-то не так логично с этим решением?Наибольшее возрастающее подпоследовательность линейное время

Вот код: Без потери общности будем считать все a_i-х> 0.

#include <iostream> 
using namespace std; 
int count = 0; 
int lis(int A[], int loc, int length, int ** table, int max_so_far=0){ 
count++; 
    if (loc == length) 
    return 0; 

    if (table[loc][max_so_far] != -1) 
     return table[loc][max_so_far]; 

int val1 = 0, val2 = 0; 
val1 = lis(A, loc+1, length, table, max_so_far); 
if (max_so_far < A[loc]) 
    val2 = 1 + lis(A, loc+1, length, table, A[loc]); 
    table[loc][max_so_far] = max(val1,val2); 
return max(val1,val2); 
} 

int main(){ 
int A[]={10, 11, 12, 9, 8, 7, 5, 6}; 
    int A[]={1,3,2,5,1,3,2,5,1,3,2,5,1,3,2,5,1,3,2,5,1,3,2,5,1,3,2,5, 1,3,2,5, 1,3,2,5, 1,3,2,5, 1,3,2,5, 1,3,2,5}; 
    int ** table; 
int n = 49; 
    int range = 6; 
table = new int*[n]; 
    for (int i =0;i<n;i++){ 
     table[i] = new int[range]; 
     for(int j=0;j<range;j++) 
     table[i][j] = -1; 
} 
    count = 0; 
    cout<<lis(A, 0, n, table, 0)<<endl; 
cout<<"Number of calls made: "<<count<<endl; 
    return 0; 
}

источник

2013-12-06 user3073924

Это просто запутанным и пространство неэффективный способ написать стандартный вывод алгоритма (п^2).

источник

2013-12-06 11:05:10 chill

Спасибо за ваш комментарий. Но суть не в коде, а в том, что это время работы этой проблемы, и я считаю, что это не O (n^2) в этой реализации. – user3073924

Время работы O (n^2) в худшем случае и в среднем. – chill

Спасибо за инструкцию, но инициализация таблицы n * max {a_i}, очевидно, не n^2. И значение lis() вычисляется не более n * max {a_i} раз, так как значения сохраняются там. Пожалуйста, объясните, почему вы думаете, что это O (n^2). – user3073924

Я не вижу в этом ничего плохого. Сложность - это, как вы говорите, O (n * | A |), где | A | - количество уникальных элементов. В худшем случае | A | = n.

источник

2013-12-06 11:29:00

Спасибо. Да, я считаю, что без таблицы initializatin это действительно O (n * | A |), или если мы использовали таблицу [int] [hashmap >] вместо таблицы [int] [int], мы сделали бы среднее время работы O (n * | A |) Я верю. Но да, дело в том, что для моей реализации таблицы это должно быть O (n * max {a_i}). Однако я попытался решить эту проблему всюду и нашел только решения O (n^2) или O (nlogn). Это страница википедии тоже: http://en.wikipedia.org/wiki/Longest_increasing_subsequence. Это основная причина, по которой я думал, что у меня что-то не так. – user3073924

Наибольшее возрастающее подпоследовательность линейное время

ответ

Смежные вопросы