1.2 算法分析

算法分析主要用于分析算法占用计算机资源的情况，可围绕时间和空间两方面展开，分为算法的时间复杂度分析和算法的空间复杂度分析，根据分析情况选择算法或对算法进行改进和优化。评价算法效率的方法有两种：事前分析法和事后评估法。事后评估法是指先将算法通过计算机语言转换为程序，由计算机运行过后，统计它所耗费的时间和占用的资源。这种方法有一定缺陷，首先是必须运行，如果有多个算法的话，还要逐个执行一遍，之后再做比较，这样比较耗费时间和精力；其次是在程序运行过程中，有可能受到各种外部因素的影响，使评估结果产生偏差。因此在实际应用中，大多使用事前分析法来评估算法效率。

算法的运行时间主要和问题的规模n有关，例如参与运算的元素个数等，算法的复杂度描述的是算法的运行时间与问题规模之间的关系。通常情况下，用算法中基本语句的运行时间来衡量算法的运行时间。基本语句通常是除去分支结构和循环结构之外的语句，被执行次数最多的语句，一般是指最内层循环中的语句。