facebook

[_reality]

что-то сомнительно на счет O(n), хотя бы потому что количество сиквенсов может быть больше n, как их все можно составить и уложиться в n не понятно. Хоть раз но будет же итерация на каждый сиквенс, тот же последний элемент добавляем. Вот - уже больше N. Если не так, то поясните как это O(n) получается. Если конечно мы одно и то же имеем ввиду

если считать операции вставки в список то думаю да, получится O(2^n), если считать сколько раз вызывается функция рекурсивно то O(n). если задачу оставить как вернуть все возможное подмножетства и за элементарную операцию считать хотя бы создание этого самого списка то меньше 2^n не получается

есть мнение что в задачах на dynamic programming + memorization размер key space и есть algorithmic complexity а в детали операций внутри вызова каждой функции можно не вдаваться

[alex-IT]

когда же это выяснилось...?

Да прямо на этой странице. Чукча не читатель?

Вы вбрасываете какое-то фуфло а потом называете это "выяснилось" . Вы же видели что более эффективное решение O(N^3) было приведено ?

Опровергайте

[alex-IT]

если считать операции вставки в список то думаю да, получится O(2^n), если считать сколько раз вызывается функция рекурсивно то O(n). если задачу оставить как вернуть все возможное подмножетства и за элементарную операцию считать хотя бы создание этого самого списка то меньше 2^n не получается

есть мнение что в задачах на dynamic programming + memorization размер key space и есть algorithmic complexity а в детали операций внутри вызова каждой функции можно не вдаваться

Я имел ввиду time complexity, по идее ассимптотически оно не зависит ни от чего друго кроме как от N. Мне кажется что это не тот случай когда можно описать 2^N, потому что он кардинально отличается от случая когда надо вернуть любые сабсиквенсы тем что сабсиквенсы должны монотонно возрастать. Т.е. их, сабсиквенсов будет на много (НЕ пропорционально, а на какой то порядок) меньше чем всех сабскивенсов.

[alex-IT]

Чтобы время не терять - генерировать (и записывать в output каждую в отдельности) все такие subsequences это уже практически O(N!) даже в самом простом случае когда 1,2,3,4,5,6,7,i+1
Так что n*log(n) точно не получится
Максильмальный subsequence в n*lon(n) решается с помощью TreeMap

Вы имеете ввиду максимальный возрастающий сабсиквенс? Если так, то все возрастающие сабсиквенсы должны решаться в N^2 Log N

[alex-IT]

del

[voyager3]

Чтобы время не терять - генерировать (и записывать в output каждую в отдельности) все такие subsequences это уже практически O(N!) даже в самом простом случае когда 1,2,3,4,5,6,7,i+1
Так что n*log(n) точно не получится
Максильмальный subsequence в n*lon(n) решается с помощью TreeMap

Вы имеете ввиду максимальный возрастающий сабсиквенс? Если так, то все возрастающие сабсиквенсы должны решаться в N^2 Log N

Ну выведите все возрастающие подпоследовательности (1, 2,3,4,5,6,7,8,9,10)

[oshibka_residenta]

Ну выведите все возрастающие подпоследовательности (1, 2,3,4,5,6,7,8,9,10)

Зачем так сложно. Пусть это будет ( 1, 2,3,4,5 )

[alex-IT]

Ну выведите все возрастающие подпоследовательности (1, 2,3,4,5,6,7,8,9,10)

Зачем так сложно. Пусть это будет ( 1, 2,3,4,5 )

их 26, верно?

[АццкоМото]

когда же это выяснилось...?

Да прямо на этой странице. Чукча не читатель?

Вы вбрасываете какое-то фуфло а потом называете это "выяснилось" . Вы же видели что более эффективное решение O(N^3) было приведено ?

Опровергайте

Чего тут опровергать-то? Если вывод одного результат на экран О(1), то вывод 2**N-N-1 результатов - О(2**N) - даже не нужно смотреть в алгоритм, чтобы понять, что быстрее невозможно

[АццкоМото]

Чтобы время не терять - генерировать (и записывать в output каждую в отдельности) все такие subsequences это уже практически O(N!) даже в самом простом случае когда 1,2,3,4,5,6,7,i+1
Так что n*log(n) точно не получится
Максильмальный subsequence в n*lon(n) решается с помощью TreeMap

Вы имеете ввиду максимальный возрастающий сабсиквенс? Если так, то все возрастающие сабсиквенсы должны решаться в N^2 Log N

Ну выведите все возрастающие подпоследовательности (1, 2,3,4,5,6,7,8,9,10)

шо, все 1013 штук?

[alex-IT]

Чтобы время не терять - генерировать (и записывать в output каждую в отдельности) все такие subsequences это уже практически O(N!) даже в самом простом случае когда 1,2,3,4,5,6,7,i+1
Так что n*log(n) точно не получится
Максильмальный subsequence в n*lon(n) решается с помощью TreeMap

Вы имеете ввиду максимальный возрастающий сабсиквенс? Если так, то все возрастающие сабсиквенсы должны решаться в N^2 Log N

Ну выведите все возрастающие подпоследовательности (1, 2,3,4,5,6,7,8,9,10)

шо, все 1013 штук?

Да, однако действительно сложность будет O(2^N). O(N^3) не возможно сделать. Другое дело если надо найти тьлько один максимальной длины или суммы, то N^2 и N Log N возможны

[АццкоМото]

Да, однако действительно сложность будет O(2^N). O(N^3) не возможно сделать. Другое дело если надо найти тьлько один максимальной длины или суммы, то N^2 и N Log N возможны

одна возрастающая подпоследовательность максимальной длины/суммы и вовсе тривиально находится за линейное время

[Dweller]

Да, однако действительно сложность будет O(2^N). O(N^3) не возможно сделать. Другое дело если надо найти тьлько один максимальной длины или суммы, то N^2 и N Log N возможны

одна возрастающая подпоследовательность максимальной длины/суммы и вовсе тривиально находится за линейное время

линейный код в студию!

я пока только за N Log N могу

public static List<Integer> longest_increasing_subsequence(List<Integer> sequence) {
int[] lab = new int[sequence.size()];
TreeMap<Integer,Integer> sm = new TreeMap<Integer, Integer>();
lab[0] = 1;
sm.put(sequence.get(0), 1);
for (int i = 1; i<sequence.size(); i++) {
Integer key = sm.ceilingKey(sequence.get(i));
if (key != null) {
lab = sm.get(key);
sm.remove(key);
sm.put(sequence.get(i), lab);
} else {
lab = sm.size()+1;
sm.put(sequence.get(i), lab);
}
}
List<Integer> ou = new ArrayList<Integer>();
int tailcnt = sm.size();
for (int i=sequence.size()-1; i>=0 && tailcnt > 0; i--) {
while (tailcnt != lab && i>0)
i--;
ou.add(sequence.get(i));
tailcnt--;
}
Collections.reverse(ou);
return ou;
}

[АццкоМото]

Да, однако действительно сложность будет O(2^N). O(N^3) не возможно сделать. Другое дело если надо найти тьлько один максимальной длины или суммы, то N^2 и N Log N возможны

одна возрастающая подпоследовательность максимальной длины/суммы и вовсе тривиально находится за линейное время

линейный код в студию!

я пока только за N Log N могу

public static List<Integer> longest_increasing_subsequence(List<Integer> sequence) {
int[] lab = new int[sequence.size()];
TreeMap<Integer,Integer> sm = new TreeMap<Integer, Integer>();
lab[0] = 1;
sm.put(sequence.get(0), 1);
for (int i = 1; i<sequence.size(); i++) {
Integer key = sm.ceilingKey(sequence.get(i));
if (key != null) {
lab = sm.get(key);
sm.remove(key);
sm.put(sequence.get(i), lab);
} else {
lab = sm.size()+1;
sm.put(sequence.get(i), lab);
}
}
List<Integer> ou = new ArrayList<Integer>();
int tailcnt = sm.size();
for (int i=sequence.size()-1; i>=0 && tailcnt > 0; i--) {
while (tailcnt != lab && i>0)
i--;
ou.add(sequence.get(i));
tailcnt--;
}
Collections.reverse(ou);
return ou;
}

вы сейчас серьезно или издеваетесь? эта задача ничем по сути не отличается от поиска максимума в массиве. хранишь индексы начала и конца самой длинной пока что встреченной последовательности и такие же индексы для изучаемой на данном этапе. как только находим очередной элемент, что меньше предыдущего, значит текущая последоовательность прервалась. если она длиннее, чем предыдущая самая большая, обновляем индексы начала-конца, иначе - просто идем дальше

я могу, конечно, напейсать код. но скучно же

[Dweller]

я могу, конечно, напейсать код. но скучно же

А вот тут можно будет написаный линейный код протестировать
https://www.hiredintech.com/classrooms/ ... 12/task/14

[АццкоМото]

я могу, конечно, напейсать код. но скучно же

А вот тут можно будет написаный линейный код протестировать
https://www.hiredintech.com/classrooms/ ... 12/task/14

т.е. вы все-таки серьезно? и даже словесное описание вас не убедило?

[Dweller]

я могу, конечно, напейсать код. но скучно же

А вот тут можно будет написаный линейный код протестировать
https://www.hiredintech.com/classrooms/ ... 12/task/14

т.е. вы все-таки серьезно? и даже словесное описание вас не убедило?

Там тоже есть словесное описание
И до линейного решения почему-то не додумались

[АццкоМото]

я могу, конечно, напейсать код. но скучно же

А вот тут можно будет написаный линейный код протестировать
https://www.hiredintech.com/classrooms/ ... 12/task/14

т.е. вы все-таки серьезно? и даже словесное описание вас не убедило?

Там тоже есть словесное описание
И до линейного решения почему-то не додумались

Значит, мы по-разному понимаем задачу.

Ещё раз: нужно найти возрастающую подпоследовательность максимальной длины/суммы? Это тривиально за линейное время. Или всё же что-то другое?

[АццкоМото]

ЗЫ. Доступа к странице по ссылке у меня нет. Можете скопировать сюда описание задачи?

[_reality]

вы сейчас серьезно или издеваетесь? эта задача ничем по сути не отличается от поиска максимума в массиве. хранишь индексы начала и конца самой длинной пока что встреченной последовательности и такие же индексы для изучаемой на данном этапе. как только находим очередной элемент, что меньше предыдущего, значит текущая последоовательность прервалась. если она длиннее, чем предыдущая самая большая, обновляем индексы начала-конца, иначе - просто идем дальше

я могу, конечно, напейсать код. но скучно же

Подпослдеовательность не обязательно должна быть continuous, к примеру в [2, 12, 3, 14, 5, 6] - это должна быть [2, 3, 5, 6]. В "классической" задаче longest increasin sub-seq это так.

[АццкоМото]

вы сейчас серьезно или издеваетесь? эта задача ничем по сути не отличается от поиска максимума в массиве. хранишь индексы начала и конца самой длинной пока что встреченной последовательности и такие же индексы для изучаемой на данном этапе. как только находим очередной элемент, что меньше предыдущего, значит текущая последоовательность прервалась. если она длиннее, чем предыдущая самая большая, обновляем индексы начала-конца, иначе - просто идем дальше

я могу, конечно, напейсать код. но скучно же

Подпослдеовательность не обязательно должна быть continuous, к примеру в [2, 12, 3, 14, 5, 6] - это должна быть [2, 3, 5, 6]. В "классической" задаче longest increasin sub-seq это так.

Аааа
Понял, перезарядил. Тут таки да, линейное время едва ли достижимо. Хотя и есть над чем пораскинуть мозгами — если не в плане биг-О для худшего случая, то а плане практической фефективности

[Dweller]

вы сейчас серьезно или издеваетесь? эта задача ничем по сути не отличается от поиска максимума в массиве. хранишь индексы начала и конца самой длинной пока что встреченной последовательности и такие же индексы для изучаемой на данном этапе. как только находим очередной элемент, что меньше предыдущего, значит текущая последоовательность прервалась. если она длиннее, чем предыдущая самая большая, обновляем индексы начала-конца, иначе - просто идем дальше

я могу, конечно, напейсать код. но скучно же

Подпослдеовательность не обязательно должна быть continuous, к примеру в [2, 12, 3, 14, 5, 6] - это должна быть [2, 3, 5, 6]. В "классической" задаче longest increasin sub-seq это так.

Аааа
Понял, перезарядил. Тут таки да, линейное время едва ли достижимо. Хотя и есть над чем пораскинуть мозгами — если не в плане биг-О для худшего случая, то а плане практической фефективности

Именно
В случае непрерывной подпоследовательности найти максимальную длину это задача разряда найти максимум массива тоже линейно
Конечно и такое могут спросить, но надо ли тогда идти в такую контору?

[АццкоМото]

В случае непрерывной подпоследовательности найти максимальную длину это задача разряда найти максимум массива тоже линейно

Дык я даже использовал именно это выражение, когда недоумевал, о чем вообще разговор. Но, конечно, сам втупил - мог бы и догадаться.