Путаница с временными и пространственными сложностями в коде грубой силы

Недавно я искал решения проблемы, которую нашел на LeetCode. Проблему можно увидеть здесь: https://leetcode.com/articles/best-time-to-buy-and-sell-stock-ii/#

Что касается подхода грубой силы к деталям статьи, я не понимаю, почему временная сложность равна O (n ^ n). Я считаю, что это должно быть O (n!). Я также не понимаю, почему пространственная сложность равна O (N), поскольку массивы, похоже, не хранятся.

Вот код грубой силы для решения проблемы:

class Solution {
    public int maxProfit(int[] prices) {
        return calculate(prices, 0);
    }

    public int calculate(int prices[], int s) {
        if (s >= prices.length)
            return 0;
        int max = 0;
        for (int start = s; start < prices.length; start++) {
            int maxprofit = 0;
            for (int i = start + 1; i < prices.length; i++) {
                if (prices[start] < prices[i]) {
                    int profit = calculate(prices, i + 1) + prices[i] - prices[start];
                    if (profit > maxprofit)
                        maxprofit = profit;
                }
            }
            if (maxprofit > max)
                max = maxprofit;
        }
        return max;
    }
}

java stock time-complexity space-complexity brute-force
person D-Studios    schedule 20.04.2020    source источник
comment
Я считаю, что это должно быть O(n!), не могли бы вы объяснить, почему вы так думаете?   -  person akuzminykh    schedule 20.04.2020
comment
@akuzminykh Внешний цикл похож на n, а внутренний цикл - на n-1. И тогда внешний цикл становится n-1, а внутренний цикл становится n-2. И так далее   -  person D-Studios    schedule 20.04.2020
comment
@ D-Studios, вы заметили рекурсивный вызов, вот что делает его экспоненциальным?   -  person Abhinav Chauhan    schedule 20.04.2020
comment
@D-Studios Формально правильное доказательство в этом случае немного сложное, вам нужно много писать. Но поверьте мне, это O(n^n). Если/когда у меня будет время, я отправлю доказательство здесь.   -  person akuzminykh    schedule 20.04.2020
comment
@akuzminykh Мои эмпирические данные говорят об обратном, т.е. O(2^n), а не O(n^n).   -  person Andreas    schedule 20.04.2020

Ответы (1)


arrow_upward
2
arrow_downward

Давайте попробуем с эмпирическими данными, т.е. посчитаем стоимость.

В худшем случае prices расположены в порядке возрастания, поэтому if (prices[start] < prices[i]) всегда верно.

«Стоимостью» будет выполнение кода внутри вложенного оператора if плюс стоимость рекурсивного вызова.

Итак, чтобы принудительно подсчитать стоимость, мы изменим метод на:

public static int calculate(int n, int s) {
    int cost = 0;
    for (int start = s; start < n; start++) {
        for (int i = start + 1; i < n; i++) {
            cost++; // "cost" is the work we do here
            cost += calculate(n, i + 1); // which includes the recursive call
        }
    }
    return cost;
}

Если мы запустим с различными значениями n, мы получим:

n = 1: cost = 0, 2^n = 2, factor = 0.00
n = 2: cost = 1, 2^n = 4, factor = 0.25
n = 4: cost = 7, 2^n = 16, factor = 0.44
n = 8: cost = 127, 2^n = 256, factor = 0.50
n = 16: cost = 32767, 2^n = 65536, factor = 0.50
n = 32: cost = 2147483647, 2^n = 4294967296, factor = 0.50

Итак, мы видим, что стоимость составляет около 2^n / 2, что означает O(2^n), а не O(n^n).

Для сравнения, если мы удалим рекурсивный вызов, т.е. закомментируем эту строку кода, то получим:

n = 1: cost = 0, n^2 = 1, factor = 0.00
n = 2: cost = 1, n^2 = 4, factor = 0.25
n = 4: cost = 6, n^2 = 16, factor = 0.38
n = 8: cost = 28, n^2 = 64, factor = 0.44
n = 16: cost = 120, n^2 = 256, factor = 0.47
n = 32: cost = 496, n^2 = 1024, factor = 0.48
n = 64: cost = 2016, n^2 = 4096, factor = 0.49
n = 128: cost = 8128, n^2 = 16384, factor = 0.50
n = 256: cost = 32640, n^2 = 65536, factor = 0.50
n = 512: cost = 130816, n^2 = 262144, factor = 0.50
n = 1024: cost = 523776, n^2 = 1048576, factor = 0.50

Итак, мы видим, что стоимость составляет около n^2 / 2, что означает O(n^2), чего мы и ожидаем от вложенного цикла.

person Andreas    schedule 20.04.2020
comment
Как насчет пространственной сложности? Почему O(N)? Массив не сохраняется. - person D-Studios; 22.04.2020
comment
@D-Studios Код имеет O(n) пространственную сложность, поскольку максимальная глубина рекурсии, то есть максимальная глубина стека вызовов, линейна относительно n. - person Andreas; 22.04.2020
comment
Как вы узнали, что можно использовать 2^n. Вроде как угадали и проверили. - person D-Studios; 22.04.2020
comment
@D-Studios Я посмотрел на последовательность чисел: 7, 127, 32767, 2147483647, ... Это очень узнаваемые числа для программистов с некоторым опытом работы с двоичными числами, поэтому я подозревал 2 ^ n, вычислил его и коэффициент, чтобы подтвердите мои подозрения. - person Andreas; 22.04.2020
comment
Вы уверены, что это 2^n? Это связано с тем, что в решении указано, что временная сложность равна O (n ^ n). Кроме того, я недавно возился и нарисовал дерево расширения относительно рекурсии. Я понял, что для каждого n ветвь приведет к примерно (n-1) или (n-2) и т. д. Таким образом, в основном для каждого уровня в глубине дерева должно быть около n ^ этого числа этого уровня. Кажется, что в дереве расширения есть n уровней. Однако, хотя я думал, что это оправдывает n ^ n, я понял, что для каждого числа на каждом уровне дерева есть n ^ 2. Время больше, чем O (n ^ n)? @Андреас - person D-Studios; 22.04.2020
comment
@D-Studios Как уже говорилось в ответе, я опираюсь на эмпирические данные, которые показывают временную сложность O(2^n), а не O( п^п). Я не пытался провести математическое доказательство. Если бы временная сложность была O(n^n), то стоимость n=32 была бы ближе к 1e48, а не к ничтожным 4e9 здесь. --- На самом деле, код не показал бы никакого результата для n=32, потому что он все равно считал бы еще много лет. Причина, по которой вывод остановился на 32, заключается в том, что более высокие значения занимают слишком много времени, поэтому я отменил его. - person Andreas; 22.04.2020
comment
Я понял, что аналогичный вопрос был задан здесь: stackoverflow.com/questions/59797066/. Ответ также был O(n^n). - person D-Studios; 23.04.2020