leetcode 1011递归代码的时间复杂性问题

Question

所以我在做以下问题： https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/

我知道有一个更好的二进制搜索解决方案，但起初我想到了一个递归解决方案，我不太确定用什么最简单的方法来解释它的时间复杂性

基本上，我的蛮力方法是遍历数组的所有长度为D的前缀（每个前缀代表我们可以在第1天发送的潜在包），然后对于每个前缀，只在数组的其余部分递归，递减值为D，计算出在D-1天内装运剩余包裹的最小容量。然后，前缀和递归结果之和的最大值给出了对应于该前缀的最小容量

然后，我基本上要对所有前缀执行此操作，并获得所有前缀的最小容量。代码是这样的。。不过，我不确定我们如何在面试中轻松得出时间复杂度？（这里可能有一个bug，我只是快速记下这段代码来说明这个概念）

def shipWithinDays(weights, D):
    if D == 1:
        return sum(D)

    min_capacity = float('inf')
    capacity_till_i = 0
    for i in xrange(D):
        capacity_till_i += weights[i]
        capacity_for_remaining = shipWithinDays(weights[i+1:],D-1)

        min_capacity = min(min_capacity, max(capacity_till_i, capacity_for_remaining))

    return min_capacity

现在，我知道我们可以用大多数算法课上教的“展开法”来分析这个问题，所以 如果时间复杂度为T（n），在我的例子中，第一次递归调用后的递归将处理长度为n-1、n-2的数组，依此类推到长度为n-D的数组。这将导致如下递归关系：

T（n）=T（n-1）+T（n-2）+T（n-3）+…+T（n-D）

现在，我可以展开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

Answer 1

is there a more intuitive way to explain why its 2^n?

首先，它不是2^n。它确实是指数型的，是n次方的，但这不一定是2

一点数学知识：任何线性递归关系都允许以T(n) = a ** n形式的解，在这种情况下a是特征多项式的根

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

现在你需要证明的是有一个大于1的根，这或多或少是微不足道的。事实上，当a等于1时，左侧（即1）小于右侧（即D）。当a增长到无穷大时，LHS的增长速度比RHS快，并最终变得更大。这意味着存在a > 1，在这一点上它们是相等的

差不多就是这样。我的数学老师想多听一点。作为一名面试官，我会很高兴的

Answer 2

我猜这个问题是典型的二进制搜索。我不认为你的解决方案会通过“在线评判”，因为时间复杂度很高（你的分析可能是正确的）。但是，您可以测试您的解决方案

在面试环境中，他们所寻找的是最有效的算法，你通常可以在讨论小组中找到。他们甚至不想知道任何关于暴力算法的事情，除非这个问题可能太难了

这可能是O（N logn）时间和恒定内存：

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）。你可以告诉面试官你的时间/空间复杂性是什么。在采访中，强调“大o”通常不是一个好主意，因为他们可能有不同的观点，更不用说他们寻求实际的大o分析

我建议快速通过bio-o部分。如果面试官会有后续问题，你可以进一步展开

如果你的强项是bio-o，也许你可以花点时间在上面。通常最重要的是算法、数据结构和系统设计/架构

参考

这些是lee215的解决方案，顺便说一句，他们设计了一些LeetCode的问题，并且通常在LeetCode的讨论面板上发布最有效的解决方案

LeetCode 1011