算法分析概述
算法分析是指分析算法消耗了多少计算机资源。 另一方面,计算机资源主要是CPU时间和内存空间,分析算法消耗多少CPU时间称为时间性能分析,分析算法消耗多少内存空间称为空间性能分析。
算法分析的目的是分析算法的时空性能改进算法。
算法的时间性能分析
通常有两种方法来衡量算法的时间性能。 事后统计法和事前测算法。 事后统计法是编制算法对应程序,统计其执行时间。 一个算法用的计划
计算机语言实现后,在计算机上执行所消耗的时间,与计算机的执行速度、用于制作程序的计算机语言、因编译而产生的机器码的质量和问题的规模等多种因素相关。 这个方法的缺点有两个。 一是必须运行程序,二是有很多因素掩盖了算法的本质。
预先占有算法去掉了与这些计算机硬件、软件相关的要素,只考虑算法本身的效率的高低,一个特定算法的“执行的t .量”的大小以问题的规模(通常用整数表示)来表示)