数据结构与算法菜鸟教程：理解复杂度的概念VS两种度量方法

1. 时间空间复杂度定义文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25035.html

1) 时间复杂度文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25035.html

时间复杂度表示一个程序运行所需要的时间，其具体需要在机器环境中才能得到具体的值，但我们一般并不需要得到详细的值，只是需要比较快慢的区别即可，为此，我们需要引入时间频度（语句频度）的概念。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25035.html

时间频度中，n称为问题的规模，当n不断变化时,时间频度T(n)也会不断变化。一般情况下，算法中的基本操作重复次数的是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T（n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=Ｏ(f(n)),称Ｏ(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25035.html

2)空间复杂度文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25035.html

一个程序的空间复杂度是指运行完一个程序所需内存的大小，其包括两个部分。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25035.html

a)固定部分。这部分空间的大小与输入/输出的数据的个数多少、数值无关。主要包括指令空间（即代码空间）、数据空间（常量、简单变量）等所占的空间。这部分属于静态空间。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25035.html

b)可变空间，这部分空间的主要包括动态分配的空间，以及递归栈所需的空间等。这部分的空间大小与算法有关。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25035.html

 文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25035.html

2. 度量时间复杂度的两种方法文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25035.html

1)事后统计法文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25035.html

顾名思义，就是指在程序运行结束之后直接查看运行时间的方式进行时间复杂度的统计，通常采用利用计算机的计时器对不同算法编制的程序进行运行时间的比较，从而确认一个算法的效率。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25035.html

但这种方法有很多缺陷：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25035.html

a)特别依赖计算机环境，同一套算法可能在不同的计算机上面有着截然不同的效果，老式的计算机和现代电脑的算力完完全全不是一个级别的处理速度。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25035.html

b)算法的测试困难，有时一套算法需要海量的数据才能真正比较出效果，而为了设计这样的海量数据以及正确性，则需要花费大量的时间，而对于不同的数据，同一算法又有不一样的效果，故对于数据的使用很难去抉择。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25035.html

也正是因为有这样的缺陷，文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25035.html

2)事先估计法文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25035.html

与事后统计法不一样，事先统计法采取在计算机编译程序前对该算法进行预估的方式估算。我们可以通过利用时间频度以及函数的思维进行对时间复杂度的解析。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25035.html

3)函数符号：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25035.html

〇表示最坏情况，Ω表示最好情况，θ表示平均情况，我们常用的分析使用O进行表示即可。对于一个算法的时间复杂度而言，n表示其执行问题的规模，O(n)表示执行该问题需要的时间量级，如O(n)表示线性级别，O(n2)表示平方级别，其中n主要的判断方式为算法中循环结构的执行次数。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25035.html

以下为一些常用的基本公式：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25035.html

a)O(a）=O(1)      其中a为常数文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25035.html

b)O(an)=O(n)     其中a为常数文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25035.html

c)O(an²⁺+bn+c)=O(n²)      其中a,b,c均为常数，结果只与最大项n有关.文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25035.html