小编her*_*ant的帖子

考虑以下代码：

int array[1000000];
array[1] = 1;
array[10] = 10;

我们已经为该数组静态分配了大小为1000000的内存。但是是否全部使用了这些内存？

我的意思是如果我们改为这样做：

int *array = malloc(sizeof(int) * 1000000);
array[1] = 1;
array[10] = 10;

然后看来，实际上我们实际上使用了所有这1000000个空间：由于我们已经分配了它们，因此它们无法用于内存中的其他任何空间。但是对于静态分配的数组，事物未初始化，因此事物仍可以存储在没有设置值的其余999998点中。

本质上，我要问的是：int array[num]使用的内存将少于int array = malloc(sizeof(int) * num)。

对于我的一生，我无法描绘递归及其正在做什么。我为此很挣扎。在Competitive Programmer's Handbook 中，我发现了以下 C++ 代码片段作为以下问题的解决方案：

考虑生成一组 n 个元素的所有子集的问题。例如，{0,1,2} 的子集是 ;, {0}, {1}, {2}, {0,1}, {0,2}, {1,2} 和 {0,1 ,2}。

遍历集合的所有子集的一种优雅方法是使用递归。以下函数 search 生成集合 {0,1,...,n 的子集？1}。该函数维护一个向量子集，该子集将包含每个子集的元素。当使用参数 0 调用函数时，搜索开始。

当使用参数 k 调用函数 search 时，它决定是否将元素 k 包含在子集中，并且在这两种情况下，都使用参数 k + 1 调用自身 但是，如果 k = n，则函数注意到所有元素已处理并已生成子集。

void search(int k) {
    if (k == n) {
        // process subset
    } else {
        search(k+1);
        subset.push_back(k);
        search(k+1);
        subset.pop_back();
    }
}

可以肯定，此功能有效，我已经手动完成了大约 3 次，以查看它是否完美无缺。但为什么？

如果没有记住所有问题的所有递归解决方案，我将永远无法想出这种解决方案。这里进行了什么样的抽象？这里使用的更一般的概念是什么？

我一直在与递归作斗争，所以任何帮助表示赞赏。谢谢你。

我最近找到了以下代码：

    for (i = 0; i < k; i ++) {
        b[i] = 0x80000000;  // min integer
        s[i] = 0;
    }

以上是该程序的一部分：

int _max(int a, int b) {
    return a > b ? a : b;
}
int all_profits(int* prices, int pricesSize) {
    int i, d, p;

    p = 0;
    for (i = 1; i < pricesSize; i ++) {
        d = prices[i] - prices[i - 1];
        p = d > 0 ? p + d : p;  // get …

以下是该文件的内容：

Person Name
123 High Street
(222) 466-1234

Another person
487 High Street
(523) 643-8754

这两件事给出了相同的结果：

$ awk 'BEGIN{FS="\n"; RS="\n\n"} {print $1, $3}' file_contents

$ awk 'BEGIN{FS="\n"; RS=""} {print $1, $3}' file_contents

两种情况给出的结果是：

Person Name (222) 466-1234
Another person (523) 643-8754

RS="\n\n"其实很有道理，但是为什么RS=""也受到同样的待遇呢？

考虑从一本书，试图解释技术的“中间相遇”下面的问题- https://cses.fi/book/book.pdf（54页，PDF P64）

例如，考虑一个问题，给我们一个n个数字和一个x的列表，我们想找出是否有可能从列表中选择一些数字，使它们的和为x。例如，给定列表[2,4,5,9]且x = 15，我们可以选择数字[2,4,9]得到2 + 4 + 9 =15。但是，如果x = 10同一列表，无法形成总和。

...

解决该问题的一种简单算法是遍历元素的所有子集，并检查任何子集的总和是否为x。这种算法的运行时间为O（2 ⁿ），因为有2 ⁿ个子集。但是，通过使用中间技术，我们可以实现更有效的O（2 ^{n / 2}）时间算法。注意，O（2 ⁿ）和O（2 ^{n / 2}）是不同的复杂度，因为2 ^{n / 2}等于？2 ^ n。

1. 他们通过分割子集来扎根Big Oh时间。但是到底为什么这与原始的2 ^n有什么不同呢？

2. 说这两次是不同的。差异真的那么大吗？

3. 他们为什么不递归地归结到只有一个元素集和2 ^ 1个子集的基本情况（例如在合并排序中），而不是将它们减半？如果将它们加在一起，是否可以提高效率？

PS：我知道这本书是C ++的不好参考，但是我将它更多地用于算法说明。