目录
什么是数据结构?
学习数据结构首先要理解什么叫做数据结构。数据结构可以拆分为数据加结构，数据可以理解为未经加工的信息，结构可以理解为组织关系，所以数据结构可以简单理解为数据与数据之间的组织关系。
什么是算法?
算法可以简单理解为一系列的计算步骤，将输入数据转化为输出结果。
如何衡量一个算法的好坏？
衡量一个算法的好坏我们可以通过把它带入实际的工作环境中，想象一下我们现在刚毕业进入公司工作是一个996的工作制，那么如何平衡长期工作的压力与自身对于幸福感的追求是一个非常重要的问题，改变我们所能改变的，比如努力让自己的工作更简洁高效就是一个非常好的办法，具体到算法方面就比如让算法更简单，计算时间更短，用更专业的话来说就是优化算法效率，即优化算法的时间效率（时间复杂度）和空间效率（空间复杂度）。
什么是时间复杂度？
计算机科学中，算法的时间复杂度是一个函数，定量描述了该算法的运行时间。但理论上，一个算法执行所耗费的时间并没有实际意义，因为不同的机器所得出的时间是不同的，所以有了时间复杂度这个分析方式。具体来说就是一个算法所花费的时间与其中的语句执行次数成正比例，定义算法中基本操作的执行次数，为算法的时间复杂度。
时间复杂度的大O渐进表示法
//计算一下Func1基本操作执行了多少次？
void Func1(int N)
{
int count = 0;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
++count;
}
}
for (int k = 0; k < N; ++k) {
++count;
}
int M = 20;
while (M--) {
++count;
}
printf("%d\n", count);
}
Func1的执行基本操作次数：F(N)=N^2+N+20
●N=10 F(N)=130
●N=100 F(N)=10120
●N=1000 F(N)=1001020
实际当我们计算时间复杂度时，并不需要精确的执行次数，所以我们可以用大O渐进表示法来大概衡量一个算法的时间复杂度。
推导大O阶方法：
1、用常数1取代运行时间中所有加法常数。
2、在修改后的运行次数函数中，只保留最高阶项。
3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。
使用大O的渐进表示法后，Func1的时间复杂度为：O(N^2)
●N=10 F(N)=100
●N=100 F(N)=10000
●N=1000 F(N)=1000000
通过上面我们可以清晰地理解大O渐进表示法去掉了那些对结果影响不大的项，简洁明了地表示出了执行次数。
复杂度的:最优、平均、最差情况
举例：在一个长度为N的数组中寻找一个数据x
那么寻找到的最好结果是：1次找到
最坏结果是：第N次找到
平均情况是：N/2次找到
同理算法的复杂度的最优、平均、最差情况：
最坏情况：任意输入规模的最大运行次数（上界）
平均情况：任意输入规模的期望运行次数
最好情况：任意输入规模的最小运行次数（下界）
实际中一般情况我们关注的是算法的最坏运行情况，因为最坏情况都能达到我们需求的话，那么最好情况和平均情况就更不用担心了。
求解二分查找、递归求阶乘、递归斐波那契的时间复杂度
//计算BinarySearch的时间复杂度。
int BinarySearch(int* a, int size, int x) {
assert(a);
int left = 0;
int right = size;
while (left <= right) {
int mid = (left + right) / 2;
if (a[mid] < x) {
left = mid + 1;
}
else if (a[mid] > x) {
right = mid + 1;
}
else
return mid;
break;
}
return -1;
}
二分查找的时间复杂度：假设总共有N个元素，那么二分后每次查找的区间大小就是N，N/2，N/4，……，N/2^k（接下来操作元素的剩余个数），其中k就是循环的次数。
最坏的情况是k次二分之后,每个区间的大小为1,找到想要的元素 。
令N/2^k=1，
可得k=log2N,（是以2为底，N的对数），所以时间复杂度可以表示为O(N)=O(logN)。
//计算阶乘递归Factorial的时间复杂度。
long long Factorial(size_t N) {
return N < 2 ? N : Factorial(N - 1)*N;
}
递归求阶乘的时间复杂度：基本操作递归了N次，时间复杂度为O(N)。
//计算斐波那契递归Fibonacci的时间复杂度。
long long Fibonacci(size_t N) {
return N < 2 ? N : Fibonacci(N - 1) + Fibonacci(N - 2);
}
递归求斐波那契的时间复杂度：基本操作递归了2^N次，时间复杂度为 O(2^N)。
什么是空间复杂度？
空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。空间复杂度不是程序占用了多少的空间，算的是变量的个数。空间复杂度计算规则基本和时间复杂度类似，也使用大O的渐进表示法。
如何求空间复杂度？ 普通函数&递归函数
通常来说，只要算法不涉及到动态分配的空间，以及递归、栈所需的空间，空间复杂度通常为0(1)；若一个算法为递归算法，其空间复杂度为递归所使用的堆栈空间的大小，它等于一次调用所分配的临时存储空间的大小乘以被调用的次数(即为递归调用的次数加1，这个1表示开始进行的一次非递归调用)。
常见时间复杂度
常量阶O(1)、线性阶O（N）、平方阶O(N^2)、 对数阶O(logN)、指数阶O(2^N)。
京公网安备 11010502036488号