计算机算法是计算机科学的核心组成部分，它涉及如何有效地解决问题和执行任务。以下是对期末考试测试题中涉及的一些关键知识点的详细解释：
1. **运算时间计算**：计算算法的运行时间通常涉及对算法步骤的计数。顺序结构的时间复杂度是最简单的，即每个操作都执行一次；选择结构取决于条件满足的情况；循环结构依赖于循环次数；子过程调用涉及到递归或函数调用的开销，包括调用和返回的时间。
2. **时间复杂度表示**：T(n) = O(f(n)) 表示算法的时间复杂度上界。在题目中，第1）和2）两个等式是正确的，因为T(n) = n是线性的，可以被n²（第1）项）和log n + n（第3）项）上界。第4）等式也正确，因为两个O(log n)的乘积仍然是O(log n)。第2）等式是不正确的，因为O(n2)不能等于具体的T(n)。
3. **折半查找与顺序查找**：折半查找相对于顺序查找，时间复杂度从O(n)降低到O(log n)，因为它每次将搜索范围减半，从而显著减少了查找次数。
4. **归并排序与快速排序的分治法**：归并排序将数组分成两半，分别排序，然后合并，时间复杂度为O(n log n)。快速排序也是分治法，选取一个基准元素，划分数组，然后递归地排序两部分，平均时间复杂度同样为O(n log n)。
5. **贪心算法与背包问题**：对于一般背包问题，贪心策略不一定能得到最优解，因为选择物品时需要考虑全局最优，而贪心策略只考虑局部最优。物品的选择策略通常是根据价值密度（价值/重量）来选取。
6. **Prim与Dijkstra算法**：Prim算法选择下一个节点基于最小边权重，用于构造最小生成树，对于有负边的无向图，无法保证得到最优解。Dijkstra算法选择当前未访问节点中距离起点最近的，适用于寻找单源最短路径，负权重时也不适用。
7. **回溯法与分支限界法**：回溯法是一种试探性搜索，遇到无效路径则回退，适合找所有解。分支限界法则以剪枝函数减少搜索空间，通常更适合找最优解问题。
8. **算法时间复杂性分析**：
- 分割元素v的数组操作：时间复杂度为O(n)，因为需要遍历整个数组。
- 修改归并排序：将数组分成1/3和2/3可能导致更坏的时间复杂度，因为不平衡导致的比较次数增多，最坏情况下可能变为O(n²)。
- 流程时间复杂性：
- A1: 如果n>3，时间复杂度为O(n)，因为有n-1次f3调用。
- A2: 递归结构，最坏情况下f2和f1各执行n次，时间复杂度为O(n)。
9. **算法理解**：
- 活动安排贪心算法：选择最早结束的活动，确保无冲突。给定活动，结果应为[8,10), [9, 11:30), [11:40,13), [12,14), [13:30,15)。
- 0/1背包问题的动态规划方程：dp[i][j]表示前i个物品选择总重量不超过j的最大价值，通过状态转移方程求解。
- m-着色回溯算法：找到一个解就结束，需要添加剪枝条件以避免无效搜索。
- 分支限界法解0/1背包问题：上下界函数通常设置为当前子问题的最优解值。
10. **算法设计**：
- 判断连通图：深度优先搜索遍历图，如果每个节点都能到达，则图是连通的。
- 判断环：深度优先搜索过程中，使用visited数组记录已访问节点，如果发现反向边，则存在环。
以上是对计算机算法期末考试测试题中涉及的知识点的详细解释，涵盖了时间复杂度、算法分析、数据结构优化策略等多个重要概念。这些知识点是理解和设计高效算法的基础。
