研究生复试会问的算法分析问题及回答

1. 什么是时间复杂度和空间复杂度？

时间复杂度是算法执行所需的时间与问题规模之间的关系，通常用大O表示。空间复杂度是算法执行所需的存储空间与问题规模之间的关系，也通常用大O表示。

2. 如何计算算法的时间复杂度？

可以通过分析算法的每个步骤的时间复杂度来计算总的时间复杂度，然后使用大O表示法来表示最终的时间复杂度。

3. 如何计算算法的空间复杂度？

可以通过分析算法中使用的数据结构和变量的数量来计算算法的空间复杂度，然后使用大O表示法来表示最终的空间复杂度。

4. 什么是渐进复杂度？

渐进复杂度是指当问题规模趋近于无穷大时，算法时间复杂度或空间复杂度的增长率。通常我们只考虑最高次项，忽略低次项和常数项。

5. 什么是最优时间复杂度和最优空间复杂度？

最优时间复杂度是指在所有算法中，最快能解决问题的算法的时间复杂度。最优空间复杂度是指在所有算法中，最少使用存储空间的算法的空间复杂度。

6. 什么是稳定排序和不稳定排序？

稳定排序是指相同大小的元素在排序后仍然保持原有的相对位置关系，不稳定排序则相反。例如，冒泡排序是稳定排序，而快速排序是不稳定排序。

7. 什么是内排序和外排序？

内排序是指所有数据都能够存储在内存中进行排序，而外排序则需要借助外部存储器（如硬盘）进行排序。外排序通常需要将数据分成多个块进行排序，然后合并排序结果。

8. 什么是分治算法？

分治算法是一种算法设计策略，它将一个问题分成多个相同的子问题，然后递归地解决每个子问题，并将子问题的解合并成原问题的解。典型的分治算法包括归并排序和快速排序。

9. 什么是贪心算法？

贪心算法是一种算法设计策略，它通过每一步选择最优解来达到最终的最优解。贪心算法通常需要证明每一步选择最优解的正确性，否则可能得到次优解或者不正确的解。

10. 什么是动态规划算法？

动态规划算法是一种算法设计策略，它通过将问题分成多个相互依赖的子问题，递归地解决每个子问题，并将子问题的解合并成原问题的解。动态规划算法通常需要使用动态规划表来存储中间结果，以避免重复计算。