我知道斐波那契数列呈指数增长，因此递归算法需要呈指数增长的步数，但是 SICP v2 说树递归斐波那契算法需要线性空间，因为我们只需要跟踪我们上面的节点树。
我知道所需的步骤数与 Fib(n) 呈线性增长，但我也假设因为树呈指数级扩展，因此此事件所需的内存也需要呈指数级增长。有人可以解释为什么所需的内存只线性扩展到 N，而不是指数级吗？
维基百科以非常直观的方式（IMO）解释了依赖图，引用了一条边来自于a => b何时a依赖于b。换句话说，我们可以通过查看其邻接列表中的邻居立即找到任何给定节点的直接依赖关系（如果有）。
这似乎是实现依赖关系的明智方式；它使我们能够像执行深度优先遍历（图中每个节点的 DFS）一样轻松地执行拓扑排序。如果节点代表“任务”，那么只有当任务的所有传递依赖项都已执行/访问时，我们才能执行/访问任务。叶节点是最先被访问的，依此类推。
拓扑排序的维基百科页面将定义解释为：
在计算机科学中，有向图的拓扑排序或拓扑排序是其顶点的线性排序，使得对于从顶点 u 到顶点 v 的每个有向边 uv，u 在排序中位于 v 之前。
这与我所期望的“依赖图”相反。我们刚刚解释了如果a依赖b，则存在有向边，并且我们必须在之前a => b访问/执行。然而，根据上面解释的图，由于我们在 之前执行/访问任务，所以理所当然地取决于。因此，如果我没有记错的话，Wiki 的拓扑排序页面期望的输入图似乎是一个边缘反转的“依赖图”。页面上的算法证实了这一点；例如，他们的 DFS 方法将从一个节点开始，递归到依赖于（而不是依赖项）的节点，然后添加到某个列表的头部，以便它比其依赖项出现得更早。结果与我解释的 DFT 相同，需要明确的是，我并不是说任一页面上的任何内容都是错误的，它只是演示了执行某些操作的几种方法。b auvvunnn n
尽管 Wiki 有依赖关系图的定义，但似乎在拓扑排序页面上使用其逆，通过反向依赖关系递归，并本质上反转输出列表，这确实感觉很奇怪。
我唯一的问题是：是否有一些我遗漏的明显原因，即拓扑排序页面上的预期图形基本上与“依赖图”dfn 相反？n我们从to的依赖项遍历n，并通过记录到堆栈之类的东西来有效地反转输出，这感觉很不直观。
更一般地说，拓扑排序页面似乎期望的图无论如何似乎都不是一个好的依赖图。如果我们认为这个图是规范的“依赖图”，那么为了找到n的依赖关系，我们必须迭代整个图询问“这个节点是否指向 n？”，这看起来很奇怪。
我试图理解虚函数和虚继承.在大多数情况下,我认为我成功地掌握了它及其与多态的关系,我一直在阅读vptr如何与派生对象一起工作以及什么不是,但是下面的例子让我失望,这是我在算法和C++中的数据结构书:
#include <iostream>
using namespace std;
class Class1 {
public:
virtual void f() {
cout << "Function f() in Class1\n";
}
void g() {
cout << "Function g() in Class1\n";
}
};
class Class2 {
public:
virtual void f() {
cout << "Function f() in Class2\n";
}
void g() {
cout << "Function g() in Class2\n";
}
};
class Class3 {
public:
virtual void h() {
cout << "Function h() in Class3\n";
}
};
int main() {
Class1 object1, *p; …对于我的编程语言类,我们已经获得了一个简单的Java死锁示例,并被要求解决它.我不直接想要这个问题的答案,我主要想知道我的理解缺乏的地方.这是代码:
import java.applet.*;
import javax.swing.*;
import java.awt.*;
import java.awt.event.*;
// Attempt at a simple handshake. Girl pings Boy, gets confirmation.
// Then Boy pings girl, get confirmation.
class Monitor {
String name;
public Monitor (String name) { this.name = name; }
public String getName() { return this.name; }
// Girl thread invokes ping, asks Boy to confirm. But Boy invokes ping,
// and asks Girl to confirm. Neither Boy nor Girl can give time to their
// confirm call because …algorithm ×2
automation ×1
c++ ×1
deadlock ×1
graph ×1
inheritance ×1
java ×1
recursion ×1
tree ×1