Вопрос о временной сложности рекурсивного кода для leetcode 1011 - PullRequest
Новая
       4

Вопрос о временной сложности рекурсивного кода для leetcode 1011

1 голос
/ 17 июня 2020

Итак, я решил следующую задачу: https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/

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

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

Тогда я в основном должен сделать это для всех префиксов и получить минимальную емкость для всех префиксов. Код примерно такой ... Я не уверен, как мы легко вычисляем временную сложность во время интервью? (Здесь может быть ошибка, я просто быстро набросал этот код, чтобы проиллюстрировать концепцию.) проанализируйте это, поэтому, если временная сложность равна T (n), в моем случае рекурсии после первого рекурсивного вызова обрабатывают массив длиной n - 1, n - 2 и так далее до длины массива n - D. Это приводит к рекуррентному соотношению, например:

T (n) = T (n-1) + T (n-2) + T (n-3) + ... + T (nD)

Теперь я могу развернуть член T (n-1), и тогда я получу следующее T (n-1) = T (n-2) + T (n-3) + .... + T (n-1-D)

T (n) = 2T (n-1) + T (n-1-D) ^ Я думаю, что приведенное выше должно упроститься до 2 ^ n или что-то в этом роде? Мне кажется, что это слишком сложно с математикой, особенно в обстановке собеседования, есть ли более интуитивный способ объяснить, почему это 2 ^ n?

Ответы [ 2 ]

0 голосов
/ 17 июня 2020

Есть ли более интуитивный способ объяснить, почему это 2 ^ n?

Начнем с того, что это не 2^n. Это действительно экспоненциально, что-то в n-й степени, но это что-то не обязательно 2.

Немного математики: любое линейное рекуррентное соотношение допускает решение в форме T(n) = a ** n, где a - это root характеристического c полинома, в данном случае 

a ** D = a ** {D-1} + a ** {D-2} + ... + 1

Теперь все, что вам нужно доказать, это то, что существует root больше 1, что больше или менее тривиально. Действительно, когда a равно 1, левая часть (которая равна 1) меньше правой части (которая равна D). По мере того как a растет до бесконечности, LHS растет быстрее, чем RHS, и со временем становится больше. Значит, существуют a > 1, в которых они равны.

Это почти все. Мой внутренний учитель математики хотел бы услышать немного больше. Я, как интервьюер, был бы очень счастлив с этим.

0 голосов
/ 17 июня 2020

Думаю, это типичный вопрос двоичного поиска. Я не думаю, что даже ваше решение пройдет «Онлайн-судью» из-за большой временной сложности (и ваш анализ может быть верным). Но вы можете проверить свое решение.

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

Вероятно, это будет время O (N Log N) и постоянная память:

Python

from typing import List

class Solution:
    def shipWithinDays(self, weights: List[int], d: int) -> int:
        lo, hi = max(weights), sum(weights)
        while lo < hi:
            mid = lo + ((hi - lo) >> 1) # or mid = (lo + hi) // 2 || mid = lo + (hi - lo) // 2
            cur, required = 0, 1
            for weight in weights:
                if cur + weight > mid:
                    required += 1
                    cur = 0
                cur += weight
            if required > d:
                lo = -~mid # simply lo = mid + 1
            else:
                hi = mid

        return lo

Java

class Solution {
    public int shipWithinDays(int[] weights, int d) {
        int lo = 0;
        int hi = 0;

        for (int weight : weights) {
            lo = Math.max(lo, weight);
            hi += weight;
        }

        while (lo < hi) {
            int mid = lo + ((hi - lo) >> 1);
            int required = 1;
            int cur = 0;

            for (int weight : weights) {
                if (cur + weight > mid) {
                    required += 1;
                    cur = 0;
                }

                cur += weight;
            }

            if (required > d)
                lo = -~mid;

            else
                hi = mid;
        }

        return lo;
    }
}

C ++ 

class Solution {
public:
    int shipWithinDays(vector<int> &weights, int d) {
        int lo = 0;
        int hi = INT_MAX;

        for (int weight : weights)
            lo = max(lo, weight);

        while (lo < hi) {
            int mid = lo + ((hi - lo) >> 1);
            int required = 1;
            int cur = 0;

            for (int index = 0; index < weights.size() && required <= d; cur += weights[index++])
                if (cur + weights[index] > mid)
                    cur = 0, required++;

            if (required > d)
                lo = -~mid;

            else
                hi = mid;

        }

        return lo;
    }
};

Я бы посоветовал сосредоточить внимание на чистом коде во время интервью. Скорее всего, вам не нужно писать T (N). Вы можете просто сказать интервьюеру, какова ваша пространственно-временная сложность. Во время собеседования акцентировать внимание на «большом» обычно не стоит, потому что у них могут быть разные мнения, не говоря уже о том, что они ищут практического анализа «большого».

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

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

Ссылка

Это решение lee215 , которое, кстати, разрабатывает некоторые из этих вопросов LeetCode и обычно размещает наиболее эффективные решения на панели обсуждения LeetCode.

LeetCode 1011

...