C语言复杂度分析

文章目录 一 算法效率评估 第一，设计可靠的解法： 第二，优化解的效率： 二 迭代与递归 迭代 for 循环 递归 递归和迭代区别

一 算法效率评估 第一，设计可靠的解法：

算法需要能够在规定的输入范围内，准确无误地求解问题，确保其结果的正确性和稳定性。这是算法设计的基本要求。

第二，优化解的效率：

同一个问题往往存在多种解法，而我们的目标是在确保正确性的基础上，找到尽可能高效的算法。因此，算法效率成为衡量算法优劣的核心指标，它主要体现在以下两个维度：

时间效率： 衡量算法运行时间的长短，即算法执行所需的时间复杂度。

空间效率： 衡量算法占用内存空间的大小，即算法执行所需的空间复杂度。

简而言之，我们追求的是“既快又省”的算法设计方案，即在保证正确性的前提下，尽可能地减少时间和空间的开销。为了达到这一目标，有效地评估算法效率至关重要，因为只有通过科学的评估和对比，我们才能发现算法的改进空间，并指导后续的优化与设计工作。

效率评估方法主要分为两种：实际测试、理论估算。

实际测试 实际测试是通过编写程序运行算法或数据结构，并在指定输入规模下测量其实际运行时间和内存占用。以下是实际测试的特点： 优点： 真实反映算法在特定硬件和运行环境下的表现。 可以发现理论分析中难以捕捉的细节（如缓存命中率、指令集优化等）。 局限性： 测试结果受硬件、操作系统、编程语言等因素影响，结果不具备普适性。