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

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

0 голосов
/ 20 апреля 2020

Я недавно искал решения проблемы, которую нашел на 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;
    }
}

1 Ответ

2 голосов
/ 20 апреля 2020

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

Наихудший случай, когда 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) , что мы и ожидаем от вложенного л oop.

...