算法 | 刷题日记

1.递归通常是用栈来实现的

递归在其本质上是通过函数调用栈（Call Stack）来实现的，而不是队列（Queue）。当你调用一个函数时，该函数的局部变量、参数和返回地址会被压入（push）到一个由系统维护的调用栈中。当函数执行完毕后，这些数据会被从栈中弹出（pop），并且控制权会返回给调用者。

递归函数调用也遵循同样的模式：当一个函数（假设我们称其为A）内部调用了它自己或者另一个函数（假设我们称其为B，而B又调用了A，形成了递归），每次函数调用都会将其状态压入调用栈。当递归到达基线条件（Base Case）并开始返回时，每个函数的状态会从栈中弹出，直到最初的调用者得到结果。

队列通常用于实现迭代算法，如广度优先搜索（BFS）等。在BFS中，队列用于存储待处理的节点，并按照它们被添加到队列中的顺序进行处理。这与递归的深度优先搜索（DFS）形成对比，DFS使用栈（或隐式的函数调用栈）来按照后进先出（LIFO）的顺序处理节点。

虽然技术上可以使用队列和显式栈来模拟递归行为（例如，通过迭代实现递归算法），但这样做通常会使代码更复杂，并可能牺牲递归提供的清晰性和简洁性。然而，在某些情况下，例如处理深度非常大的递归树或需要避免栈溢出的场景，使用迭代和显式栈可能是有益的。

2.优先队列用堆来实现

优先队列（Priority Queue）的实现通常选择堆（Heap）作为其底层数据结构，而不是普通队列（Queue）。以下是几个关键原因：

1. 数据结构和操作特性：
   • 普通队列（Queue）遵循先进先出（FIFO）的原则，即最先进入队列的元素将最先被移除。
   • 优先队列（Priority Queue）则允许元素具有优先级，优先级最高的元素将最先被移除，这体现了最高级先出（first in, largest out 或 first in, smallest out，取决于优先级的定义）的行为特征。
2. 堆的性质：
   • 堆是一种特殊的树形数据结构，它可以被看作是完全二叉树或近似完全二叉树。
   • 堆总是满足堆属性：父节点的值总是大于或等于（最大堆）或小于或等于（最小堆）其子节点的值。
   • 堆提供了快速访问最大或最小元素（即堆顶元素）的能力，并且可以在对数时间内完成插入和删除操作。
3. 实现优先队列：
   • 由于堆提供了高效的插入和删除最大/最小元素的操作，因此它非常适合用于实现优先队列。
   • 当有新元素需要插入到优先队列中时，可以直接将其插入到堆中，并重新调整堆以保持堆属性。
   • 当需要从优先队列中移除最高优先级的元素时，可以直接移除堆顶元素，并重新调整堆。
4. 代码示例和设置：
   • 在C++的STL（Standard Template Library）中，priority_queue容器就是一个典型的优先队列实现，其底层就是使用堆。
   • 通过设置priority_queue的第三个模板参数（比较类），可以定义队列中元素的优先级。例如，使用greater<int>可以使队列成为小根堆，这样数字小的元素优先级更高；而默认是大根堆，数字大的元素优先级更高。

综上所述，优先队列通常使用堆作为其底层数据结构，以提供高效的插入和删除最高/最低优先级元素的操作。

3.当上下限表达式相等时，我们使用下列哪种表示法来描述算法代价? 

Θ表示法（Theta notation）用于描述算法的紧确界限，即它同时表示了算法的上限和下限复杂度。当算法的上下限复杂度相同时，Θ表示法是最合适的。