|
|
知识路径： > 计算机系统基础知识 > 计算机软件基础知识 > 数据结构与算法 > 常用算法 > 常用算法 > 算法概述 >
|
|
相关知识点：4个
|
|
|
|
|
解决同一个问题总是存在多种算法，每个算法在计算机上执行时，都要消耗时间（CPU执行指令的时间）和使用存储空间资源。因此，设计算法时需要考虑算法运行时所花费的时间和使用的空间，以时间复杂度和空间复杂度表示。
|
|
|
|
由于算法往往和需要求解的问题规模相关，因此常将问题规模n作为一个参照量，求算法的时间、空间开销和n的关系。详细分析指令的执行时间会涉及计算机运行过程的细节，因此时间消耗情况难以精确表示，所以算法分析时常采用算法的时空开销随n的增长趋势来表示其时空复杂度。
|
|
|
|
对于一个算法的时间开销T（n），从数量级大小考虑，当n增大到一定值后，T（n）计算公式中影响最大的就是n的幂次最高的项，其他的常数项和低幂次项都可以忽略，即釆用渐进分析，表示为T（n）=O（f（n））。其中，n反映问题的规模，T（n）是算法运行所消耗时间或存储空间的总量，O是数学分析中常用的符号“大O”，而f（n）是自变量为n的某个具体的函数表达式。例如，若f（n）=n2+2n+1，则T（n）=O（n2）。
|
|
|
|
|
|
语句频度（frequency count）是指语句被重复执行的次数，即对于某个基本语句，若在算法的执行过程中被执行n次，则其语句频度为n。这里的“语句”是指描述算法的基本语句（基本操作），它的执行是不可分割的，因此，循环语句的整体、函数调用语句不能算作基本语句，因为它们还包括循环体或函数体。
|
|
|
|
算法中各基本语句的语句频度之和表示算法的执行时间。
|
|
|
|
例如，对于下面的三个程序段（1）、（2）、（3），其实现基本操作“x增1”的语句++x的语句频度分别为1、n、n2。
|
|
|
|
|
|
（2）for（i=1；i<=n；i++）｛s+=x；++x；｝
|
|
|
|
|
|
|
|
|
|
因此，程序段（1）、（2）、（3）的时间复杂度分别为O（1）、O（n）、O（n2），分别称为常量阶、线性阶和平方阶。若程序段（1）、（2）、（3）组成一个算法的整体，则该算法的时间复杂度为O（n2）。
|
|
|
