数据结构介绍的复杂性

前言：数据结构终于来了。要想学好数据结构，首先要了解数据结构的复杂性。所以，什么是复杂性？

1 数据结构。

所谓。xff08的数据结构;Data Structure）计算机存储，组织数据的方式，指数据元素的集合，它们之间有一个或多个特定的关系。。

算法（Algorithm）：就是。定义良好的计算过程。，取一组或一组的值作为输入，并且产生一个或一组值作为输出。简单地说，算法是一系列计算步骤，将输入数据转换为输出结果。。

那么如何衡量一个算法的质量࿱呢？f;

2 复杂度。

编写可执行程序后的算法，运行需要时间和空间资源。。因此，测量算法的质量，一般是从。衡量时间和空间两个维度。，即。时间复杂度和空间复杂度。。

时间复杂度主要衡量算法的运行速度，空间复杂性主要衡量算法运行所需的额外空间。。

2.1 时间复杂。

定义：计算机科学，算法的时间复杂性是函数T(N)，它定量地描述了算法的运行时间。。时间复杂度是衡量程序的时间效率，那为什么不计算程序的运行时间࿱呢？f;

以下原因：

1.程序运行时间和编译环境，运行机的配置有关。在同一台机器的不同编译器上运行时间也可能不同。

2.同一算法程序在不同的机器上运行时间也会有所不同。

3.程序完成后，时间只能测试，在编写程序之前，不能通过理论思想进行计算和评估。

然后函数T(N)到底是什么？这个。T(N)函数式计算程序的执行次数。。假设计算机每个指令的执行时间基本相同（实际差异，但差别不大），然后执行次数与运行时间成正相关。执行次数可以代表程序时间效率的优缺点。

#。include。<stdio.h>#。include。<time.h>int。main。(。)。{ 。if。(。N。 ==0)。return。1。;return。Fac。(。N。-。1。)。*。N。;}。

Fac递归调用N次，N栈帧空间࿰开放c;每个栈帧使用常数空间，因此，空间的复杂性是O(N)。

3 对比常见的复杂度。