一、什么是数据结构
数据结构（Data Structure）是计算机中存储、组织数据的方式，它是数据对象、以及存在于该对象的实例和组成实例的数据元素之间的各种联系。这些联系可以通过定义相关的函数来给出。简单的来说：数据结构就是把数据元素按照一定的关系组织起来的集合，用来组织和存储数据。
数据结构是 ADT（抽象数据类型 Abstract Data Type）的物理实现。通常情况下，精心选择的数据结构可以带来效果最优效率的算法。
抽象数据类型 （Abstract Data Type， ADT ）是计算机科学中具有类似行为的特定类别的 数据结构 的 数学模型；或者具有类似语义的一种或多种 程序设计语言 的 数据类型。抽象数据类型 是描述数据结构的一种理论工具，其目的是使人们能够独立于程序的实现细节来理解数据结构的特性。抽象数据类型的定义取决于它的一组逻辑特性，而与计算机内部如何表示无关。抽象数据类型 只描述数据对象集和相关操作集“是什么”，并不涉及“如何做到”的问题。
二、数据结构的分类
传统上，我们将数据结构分为 逻辑结构 和 物理结构 两大类。
【1】、逻辑结构
逻辑结构是从具体中抽象出来的模型，是抽象意义上的结构，按照对象中数据元素之间的相互关系分类，主要分为四类：集合结构、线性结构、树形结构 和 图形结构。
①、集合结构
集合结构中的数据元素除了属于同一个集合外，它们之间没有任何其它关系。
②、线性结构
线性结构中的数据元素之间存在一对一的关系。
③、树形结构
树形结构的数据元素存在一对多的层级关系。
④、图形结构
图形结构的数据元素是多对多的关系。
【2】、物理结构
逻辑结构在计算机中真正的表现方式（又称为映像）称为 物理结构，也可以叫做 存储结构。常见的物理结构有 顺序存储结构、链式存储结构 两种。
①、顺序存储结构
顺序存储结构 就是把数据元素放到 地址连续 的存储单元里面，其数据间的逻辑关系和物理关系是一致的，比如我们常用的数据就是顺序存储结构。
顺序存储结构存在一定的弊端，就像生活中排队时有可能会有人插队，也有可能有人有特殊的情况突然离开，这时候它之后的所有元素都要向前移动或者向后移动，此时就需要链式存储结构。
②、链式存储结构
链式存储结构 是把元素存放在 任意的 存储单元里面，这组存储单元可以是连续的也可以是不连续的。此时，数据元素之间并不能反映元素间的逻辑关系，因此在链式存储结构中引进了一个 指针 来存放数据元素间的地址，这样通过地址就可以找到相关关联元素的位置。
二、什么是算法
算法（Algorithm）是一个 有限指令集，它可以 接受一些输入（有些情况下不需要输入），在经历 有限步骤 之后会终止，并且会产生 一个输出。算法中的每条指令都应该必须有充分明确的目标，不可以有歧义。每条指令都应该在计算机能处理的范围之内运行。算法中每一条指令的描述都应该抽象，不应该依赖于任何一种计算机语言以及具体的实现手段。
三、算法的分析
算法 是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间，空间或效率来完成同样的任务。一个算法的优劣可以用 空间复杂度 与 时间复杂度 来衡量。
【1】、空间复杂度 S(n)
根据算法写成的程序在执行时 占用存储单元的长度。这个长度往往与输入数据的规模有关。空间复杂度过高的算法可能导致使用的内存超限，造成程序非正常中断。
【2】、时间复杂度 T(n)
在进行算法分析时，语句总的执行次数 T(n) 时关于问题规模 n 的函数，进而分析 T(n) 随着 n 的变化情况并确定 T(n) 的量级。算法的时间复杂度，就是算法的时间量度，记作：T(n) = O(f(n))。它表示随着时间规模 n 的增大，算法执行实际爱你的增长率和 f(n) 的增长率相同，称作算法的渐进时间复杂度，简称 时间复杂度，其中 f(n) 是问题规模 n 的某个函数。
时间复杂度过高的低效算法可能导致我们在有生之年都等不到运行结果。算法的时间复杂度分析主要分为两种方法：事后分析估算方法 和 事前分析估算方法。
①、事后分析估算方法
事后分析估算方法主要是通过设计好的测试程序和测试数据，利用计算机定时器对不同算法编制的程序的运行时间进行比较，从而确定算法效率的高低。
在 C 语言中提供了一个 clock() 函数，它可以捕捉从程序开始运行到 clock() 被调用时所花费的时间。这个时间单位是 clock tick，即 ”时钟打点“，常数 CLK_TCK 就是机器时钟每秒所走的时钟打点数。
#include <stdio.h>
#include <time.h>
clock_t start,stop; // clock_t是clock()函数返回的变量类型
double duration; // duration用来记录被测函数运行时间，以秒为单位
int main()
{
// 不在测试范围内的准备工作写在clock()调用之前
start = clock(); // 开始计时
MyFunction(); // 被测函数加在这里
stop = clock(); // 结束计时
duration = ((double)(stop - start)) / CLK_TCK;
// 其它不再测试范围的处理写在后面，例如输出duration的值
return 0;
}
事后分析估算方法有很大的缺陷：必须依据算法实现编制好的测试程序，通常要花费大量时间和精力，测试完了如果发现测试的是非常糟糕的算法，那么之前所作的事情就全部白费了，并且不同的测试环境（硬件环境）的差异导致测试的结果差异也很大。
如果程序执行太快，我们有可能会得不到正确的运行时间。这时，我们可以让被测函数 重复运行 多次，使得测出的总的时钟打点间隔充分长，最后计算被测函数 平均每次 运行的时间即可。
②、时间分析估算方法
在计算机程序编写前，依据统计方法对算法进行估算，经过总结，我们发现一个高级语言编写的程序在计算机上运行所消耗的时间取决于以下因素：（1）、算法采用的策略和方案；（2）、编译产生的代码质量；（3）、问题的输入规模；（4）、机器执行指令的速度；
由此可见，抛开这些与计算机硬件、软件有关的因素，一个程序的运行时间依赖于算法的好坏和问题的输入规模。如果算法固定，那么该算法的执行时间就只和问题的输入规模有关了。
我们在比较算法随输入规模的增长量时，可以得到以下结论：
- 算法函数的常数可以忽略；
- 算法函数中最高次幂的常数因子可以忽略；
- 算法函数中最高次幂越小，算法效率越高；
在这里，我们可以近似可以认为：执行次数 = 执行时间。
我们常用大写的 O 来表示算法的时间复杂度，这种表示方法也被称为 大O表示法。一般情况下，随着输入规模 n 的增大，T(n) 增长最慢的算法为最优算法。
基于我们在比较算法随输入规模的增长量时得到的结论，我们可以推到出 大O表示法 有以下几个规则可以使用：
- 用常数 1 取代运行时间中所有加法常数；
- 在修改后的运行次数中，只保留最高项；
- 如果最高阶存在，且常数因子不为 1，则去除这个项相乘的常数；
时间复杂度从低到高依次为：O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3)
随着输入规模的增大，时间成本会急剧增大。所以，我们的算法，尽可能的追求是 O(1)、O(n)、O(nlogn) 这几种时间复杂度，而如果发现算法的时间复杂度为平方阶、立方阶或者更复杂的，那我们可以认为这种算法是不可取的，需要优化。
在分析一般算法的执行效率时，我们经常关注两种复杂度：最坏平均复杂度 \(T_{worst}(n)\) 和 平均复杂度 \(T_{avg}(n)\)。最坏情况是一种保证。在应用中，这时一种最基本的保障，即使在最坏的情况下，也能够正常提供服务。所以，除非特别指定，我们提到的运行时间都指的是最坏情况下的运行时间。
标签：01,clock,复杂度,算法,概述,时间,数据结构,结构 From： https://www.cnblogs.com/kurome/p/17218048.html一个 for 循环的时间复杂度等于循环次数乘以循环体代码的复杂度；
if-else if-else 结构的复杂度取决于 if 的条件判断复杂度和多分支部分的复杂度，总体复杂度取最大的一个；