数据结构和算法初学者指南：理解复杂性概念与两种测量方法

1。时间和空间复杂度的定义

1) 时间复杂度

时间复杂度表示程序运行所需的时间。具体值需要在机器环境下获取，但一般我们不需要获取详细值，只需比较速度和速度的差异即可。为此，我们必须引入时间频率（话语频率）的概念。

在时间频率中，n 称为问题的规模。随着n不断变化，时间频率T(n)也会不断变化。一般来说，算法中基本操作的重复次数是问题大小n的函数，用T(n)表示。如果当n趋于无穷大时，存在一些辅助函数f(n)，T（n的极限值）/f(n)是非零常数，则f(n)被称为同阶函数： T(n)。记为T(n)=O(f(n))，O(f(n))称为算法的渐近时间复杂度，简称时间复杂度。

2）空间复杂度

程序的空间复杂度是指运行该程序所需的内存量，它由两部分组成。

a) 固定部分。该空间的大小与输入/输出数据的数量和值无关。主要包括指令空间（即代码空间）、数据空间（常量、简单变量）等占用的空间，这部分是静态空间。

b) 可变空间。这部分空间主要包括动态分配的空间和递归栈所需的空间。这部分空间的大小与算法有关。 ？使用计算机定时器来比较不同算法编译的程序的运行时间，以确认算法的效率。

但是这种方法有很多缺点：

a) 特别依赖计算机环境。同一套算法在不同的计算机上可以产生完全不同的效果。老式计算机和现代计算机的计算能力有很大不同。处理速度级别。

b) 测试算法很困难。有时候一套算法需要大量的数据才能真正比较效果。设计如此海量的数据并确保正确性需要花费大量时间。对于不同的数据，相同的算法有不同的效果，因此很难选择使用的数据。

正是因为这个误差，

2）事前估算方法

与事后统计方法不同。事前统计方法在计算机编译程序之前估计算法。我们可以使用时间频率和函数思维来分析时间复杂度。

3) 功能符号：

〇代表最坏情况，Ω代表最好情况，θ代表平均情况。我们常用的分析可以用O来表示。对于算法的时间复杂度来说，n表示其执行问题的程度，O(n)表示执行问题所需的时间。例如，O(n)表示线性级别，O(n2)表示二次级别，其中n的主要判断方法是算法中循环结构的执行次数。

以下是一些常用的基本公式：

a)O(a)=O(1) 其中a是常数

b)O(an)=O(n) 其中a是常数

c )O(an2++bn+c)=O(n2) 其中 a、b、c 是常数，结果仅适用于最大项 n。