facebook

[# SPIRITUS #]

Как сделать с O(n) ?

http://www.geeksforgeeks.org/largest-su ... -subarray/
https://en.wikipedia.org/wiki/Maximum_subarray_problem

Блдж, как меня такие вопросы выбешивают. Решение за линейное время было придумано "вскорости после" формулировки задачи, всего через примерно 7 лет, профессором Карнеги Меллона. А ты, нигра, давай мне на интервью за 40 минут сообрази

Ну, конкретно эта задачка еще ничего, корявый O(n) вариант можно придумать не зная истории с профессором, проверено. Другое дело, что не получится сразу выдать код такой же чистоты и компактности, рабочий O(n) можно упрощать гораздо дольше, чем придумывать. Она есть (без решения) в одной из начальных глав CLRS (которая Комен в народе), оттого и на интервью должна встречаться довольно часто.

[alex-IT]

вот задачка -

Code: Select all

Given an integer array, find all the different possible increasing subsequences of the given array, and the length of an increasing subsequence should be at least 2 .
Example:

Input: [4, 6, 7, 7]
Output: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]

input: [2,1,3]
output: [2, 3] [1, 3]

Чтобы время зря не терять - если в циклах текущий элемент больше (или равен) какому либо из предыдущих, то
1 - добавляем эту пару в increasing subsequence
2 - добавляем все ранее накопленные subsequences для меньшего из той самой пары СПЛЮСОВАННЫЕ с текущим элементом.

что-то типа

Code: Select all

//начинаем со второго элемента
for (i=1;i<sizeof(ary);i++) {
        for(j=0;j<i;j++) {       
            if(ary[i]>=ary[j]) {          
                if(isset(hash[j])){
			// собираем все что было в hash[j] + ary[i]   
			//Loop through hash[j]
                    }
                }
                hash[i][]=array(ary[j],ary[i]);
            }
        }
    }

Как нетрудно видеть сложность O(N^3)(хоть и максимальная) - 2 петли, да еще и накопленные элементы плюсовать с текущим, еще петля
В интернете полно задачек где нужно вернуть лишь максильмальный subsequence, что легко решается в O(N^2) и посложнее решается в O(N Log N)
Можно ли данную задачку решить в O(N^2) или даже в O(N Log N) ?
Предлагаю постить псевдокод) там меньше лишнего

[Dweller]

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

[alex-IT]

должно быть O(n^3)-две петли и внутри ко всем hash(i) добавляем ary(i) откуда же там O(N!)
если бы нужно было вернуть только максимальный сиквенс или сосчитать кол-во сиквенсов (не составляя все секвенсы) то O(n^2) и O(n log n) точно делается. Полно решений в интернете.
подозреваю что данную задачу можно сделать с O(n^2 log N)

[АццкоМото]

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

да где же вы факториал-то увидели? долбаный стыд

[oshibka_residenta]

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

да где же вы факториал-то увидели? долбаный стыд

Число подпоследовательностей длины к : n!/k!/(n-k)!

[Larsonsager]

Как сделать с O(n) ?

http://www.geeksforgeeks.org/largest-su ... -subarray/
https://en.wikipedia.org/wiki/Maximum_subarray_problem

Блдж, как меня такие вопросы выбешивают. Решение за линейное время было придумано "вскорости после" формулировки задачи, всего через примерно 7 лет, профессором Карнеги Меллона. А ты, нигра, давай мне на интервью за 40 минут сообрази

Ну, не знаю. Видел решение на http://e-maxx.ru/algo/maximum_average_segment . Там два решения, и оба за линейное время. Первое названо очевидным, но я в нём пытался разобраться минут десять. А второе объявлено более сложным для понимания (как раз которое решил чувак из Карнеги 7 лет спустя), но я его как раз придумал сам за несколько минут. Наверно, хороший алгоритмист видит какие-то тонкости и хочет обосновать какие-то слабые места, а я как неалгоритмист даже не заметил этих трудностей и без должной скрупулезности нашел алгоритм, недостаточно убедительно доказав его корректность. Но алгоритм оказался правильным, а для меня - и более простым, чем тот, который "практически очевиден".

[АццкоМото]

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

да где же вы факториал-то увидели? долбаный стыд

Число подпоследовательностей длины к : n!/k!/(n-k)!

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

Так что для 1, 2, 3 ... N будет ровно 2^N - N - 1.
Иными словами: каждый элемент можно либо включить в результат, либо нет (2^N), но не подходят последовательности из ровно одного элемента (-N) и пустая (-1)

Факториалы же появляются, когда возможны перестановки

[oshibka_residenta]

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

да где же вы факториал-то увидели? долбаный стыд

Число подпоследовательностей длины к : n!/k!/(n-k)!

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

Так что для 1, 2, 3 ... N будет ровно 2^N - N - 1.
Иными словами: каждый элемент можно либо включить в результат, либо нет (2^N), но не подходят последовательности из ровно одного элемента (-N) и пустая (-1)

Факториалы же появляются, когда возможны перестановки

Факториалы появляются когда есть выборка. И, конечно, нужно просто о k просуммировать и получится 2^n, как вы точно заметили. Пойнт в том, что это сильно больше n^3
Google: binomial coefficients

[АццкоМото]

И, конечно, нужно просто о k просуммировать и получится 2^n, как вы точно заметили.

Это называется "мы не ищем легких путей" Получить не самую простую формулу для выборки к из н, потом просуммировать по к 1..н и сообразить, что на выхлопе получается 2**н.... при том что любая выборка из н однозначно описывается последовательностью из н бит и, следовательно, уши 2**н торчат просто со всей очевидностью и не требуют уаще ни одного даже самого простейшего вычисления

Пойнт в том, что это сильно больше n^3
Google: binomial coefficients

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

[oshibka_residenta]

И, конечно, нужно просто о k просуммировать и получится 2^n, как вы точно заметили.

Это называется "мы не ищем легких путей" Получить не самую простую формулу для выборки к из н, потом просуммировать по к 1..н и сообразить, что на выхлопе получается 2**н.... при том что любая выборка из н однозначно описывается последовательностью из н бит и, следовательно, уши 2**н торчат просто со всей очевидностью и не требуют уаще ни одного даже самого простейшего вычисления

Видимо я больше математик чем программист. формулу для выборки к из н я помню с 7(?) класса. Свел задачу к предыдущей.

[Dweller]

Согласитесь что 2^N это ближе к факториалу чем к n^2
Экспонента против полинома

[АццкоМото]

Оно, конечно, ближе, но какая разница?

Вообще интересно, вроде выше приводилось решение за кубическое время. Правда, я его не читал. Типа неверное чоле?

[oshibka_residenta]

Вообще интересно, вроде выше приводилось решение за кубическое время. Правда, я его не читал. Типа неверное чоле?

Так о чем и речь. Правильное решение- рекурсия. Где в функцию в качестве параметров передается текущая подпоследовательность (слева) и остаток последовательности справа, который надо перебрать. И внутри для каждого элемента справа опять эту же функцию вызываем

[АццкоМото]

Вообще интересно, вроде выше приводилось решение за кубическое время. Правда, я его не читал. Типа неверное чоле?

Так о чем и речь. Правильное решение- рекурсия. Где в функцию в качестве параметров передается текущая подпоследовательность (слева) и остаток последовательности справа, который надо перебрать. И внутри для каждого элемента справа опять эту же функцию вызываем

Да, как-то так, и подход тащемта стандартный, тривиальный и давно надоевший.

Единственное, что напрягает, это что в рамках блабла на привете можно с лёгкостью найти не только ассимптотическую сложность, но и worst case scenario output size с точностью до единицы практически не задействовав остатки мозга. А вот на интервью можно обосраться как с биг-о комплексити правильного решения, так и не суметь доказать, что быстрее никак. Проблеять нечто невразумительное, выйти на улицу и через 5 минут понять все до конца

У кого как, а у меня подобное было неоднократно.

[Dweller]

Оно, конечно, ближе, но какая разница?

Вообще интересно, вроде выше приводилось решение за кубическое время. Правда, я его не читал. Типа неверное чоле?

Я поэтому и говорю что это практически факториал а не бля буду факториал

[_reality]

Я утверждаю что по скольку размер memo зависит от длины списка то сложность этого алгоритма O(n) поскольку максимум требуется заполнить только n ключей, после этого будет O(1) lookup. Хз как это называется, amortized complexity может быть или как то так

Code: Select all

def compute(input: Seq[Int]): Seq[Seq[Int]] = {
      
    val memo = mutable.Map.empty[Seq[Int], Seq[Seq[Int]]]
      
    def run(seq: Seq[Int]): Seq[Seq[Int]] = memo.getOrElseUpdate(seq, seq match {
        case Nil      => Seq(Seq.empty)
        case x :: Nil => Seq(Seq(x))
        case x :: xs  =>
          val candidates = seq.zipWithIndex.tail.filter { case (value, idx) => value >= x }
          val res = candidates.map { case (value, idx) => run(seq.drop(idx)).map(x +: _) }
          res.flatten
    }) 
      
    val res = for (i <- 0 to input.length) yield run(input.drop(i))   
    res.flatten.filter(_.length >= 2)
}

[_reality]

del

[АццкоМото]

Оно, конечно, ближе, но какая разница?

Вообще интересно, вроде выше приводилось решение за кубическое время. Правда, я его не читал. Типа неверное чоле?

Я поэтому и говорю что это практически факториал а не бля буду факториал

хренассе "практически"

[alex-IT]

Я утверждаю что по скольку размер memo зависит от длины списка то сложность этого алгоритма O(n) поскольку максимум требуется заполнить только n ключей, после этого будет O(1) lookup. Хз как это называется, amortized complexity может быть или как то так

Code: Select all

def compute(input: Seq[Int]): Seq[Seq[Int]] = {
      
    val memo = mutable.Map.empty[Seq[Int], Seq[Seq[Int]]]
      
    def run(seq: Seq[Int]): Seq[Seq[Int]] = memo.getOrElseUpdate(seq, seq match {
        case Nil      => Seq(Seq.empty)
        case x :: Nil => Seq(Seq(x))
        case x :: xs  =>
          val candidates = seq.zipWithIndex.tail.filter { case (value, idx) => value >= x }
          val res = candidates.map { case (value, idx) => run(seq.drop(idx)).map(x +: _) }
          res.flatten
    }) 
      
    val res = for (i <- 0 to input.length) yield run(input.drop(i))   
    res.flatten.filter(_.length >= 2)
}

что то в O(n) слабо верится. А можно псевдокод или любой С-подобный синтаксис вашего решения.
Я уверен что можно добиться O(N LogN) хотя знаю только как решить O(N^2) (используя hash) и O(N^3)

[АццкоМото]

Потрясающие дела. Даже после того, как выяснилось, что worst case output size is 2^N - N -1 идея решить быстрее не умерла.

[alex-IT]

когда же это выяснилось...? Опровергните что это не решается в N^3 (для простоты, на самом деле можно свести к N^2 и скорее всего к N log N)
Перебираем 1...N элементы через i, внутри перебираем от 2...i через j и сравниваем ary(i) vs ary (j) если ary(i) >ary(j) то ary(i),ary(j) это уже increasing subsequence из двух элементов, добавляем в копилочку result(i) этот маленький сабсиквенс . Да еще и добавляем накопленные subsequnces которые уже лежает в result(j) предварительно добавив элемент ary(i) к каждому из накопленных в result(j) и все это в копилочку result(i). Максимум таких добавлений будет N-1.
O(N^3)

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

[_reality]

Потрясающие дела. Даже после того, как выяснилось, что worst case output size is 2^N - N -1 идея решить быстрее не умерла.

Вот решение на Java

Code: Select all

public class IncreasingSubList {

    static class Solution {

        final List<Integer> input;

        final Map<Integer, List<List<Integer>>> memo = new HashMap<>();

        int runCnt = 0;
        int computeCnt = 0;

        public Solution(List<Integer> input) {
            this.input = input;
        }

        public List<List<Integer>> run(Integer idx) {

            runCnt += 1;

            return memo.computeIfAbsent(idx, notUsed -> {

                computeCnt += 1;

                List<Integer> list = input.subList(idx, input.size());

                List<List<Integer>> out = new ArrayList<>();

                // empty list has zero increasing sublists
                if (list.isEmpty()) {
                    out.add(new ArrayList<>());
                } else
                    // single element list hast only one increasing sublist
                    if (list.size() == 1) {
                        out.add(list);
                    } else
                    // prepend head element to all other solutions
                    {
                        Integer head = list.get(0);
                        for (int i = 1; i <= list.size(); i++) {
                            if (i == list.size() || list.get(i) >= head) run(idx + i).forEach(sol -> {
                                List<Integer> l = new ArrayList<>();
                                l.add(head);
                                l.addAll(sol);
                                out.add(l);
                            });
                        }
                    }

                return out;
            });
        }

        Set<List<Integer>> solution() {
            List<List<Integer>> solutions = new ArrayList<>();

            for (int i = 0; i < input.size(); i++) {
                solutions.addAll(run(i));
            }

            Set<List<Integer>> out = solutions.stream()
                    .filter(l -> l.size() >= 2)
                    .collect(Collectors.toSet());

            System.out.println(
                    "n = " + input.size() +
                    " run = " + runCnt +
                    " compute = " + computeCnt);

            return out;
        }

    }

    public static void main(String[] args) {

        for (int i = 1; i < 20; i ++) {
            List<Integer> input = Stream.iterate(0, n -> n + 1)
                    .limit(i)
                    .collect(Collectors.toList());
            new Solution(input).solution();
        }

        //Solution s = new Solution(Stream.of(4, 6, 7, 7).collect(Collectors.toList()));
        //s.solution().forEach(System.out::println);
    }

}

и вот такая асимптота получается

Code: Select all

n = 1 run = 1 compute = 1
n = 2 run = 4 compute = 3
n = 3 run = 8 compute = 4
n = 4 run = 13 compute = 5
n = 5 run = 19 compute = 6
n = 6 run = 26 compute = 7
n = 7 run = 34 compute = 8
n = 8 run = 43 compute = 9
n = 9 run = 53 compute = 10
n = 10 run = 64 compute = 11
n = 11 run = 76 compute = 12
n = 12 run = 89 compute = 13
n = 13 run = 103 compute = 14
n = 14 run = 131 compute = 16
n = 15 run = 161 compute = 18
n = 16 run = 193 compute = 20
n = 17 run = 227 compute = 22
n = 18 run = 263 compute = 24
n = 19 run = 301 compute = 26

space complexity 2^n-1 если требуется вернуть все списки, если надо просто посчитать то O(1), computational complexity на мой взгляд O(n)

и это кстати для худшего случая когда список идет от 1 то n то есть там точно 2^n-1 возрастающих подпоследовательностей

[alex-IT]

space complexity 2^n-1 если требуется вернуть все списки, если надо просто посчитать то O(1), computational complexity на мой взгляд O(n)

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

[oshibka_residenta]

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

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