👉数据结构👈
数据结构(Data Structure)是计算机存储、组织数据的方式，指相互之间存在一种或多种特定关系的数据元素的集合。
数据结构就是在内存中管理数据，实现增删查改的功能。知道了数据结构，不得不提一下数据库。那数据库又是什么呢？数据库其实就是在硬盘中管理数据，实现增删查改的功能。
👉算法👈
1.算法的定义
什么是算法呢？简单来说，算法就是解决问题的方法。如今普遍认为算法的定义是：
算法是解决特定问题求解步骤的一种描述，在计算机中表现为指令的有限性，并且每条指令表示一个或多个操作。
2.算法的特性
输入输出
输入和输出特性比较好理解。需要注意的是：一个算法可以具有零个或多个输入，但至少有一个或多个输出。 为什么一个算法可以没有输入，但必须要有输出呢？比如：我们需要在屏幕上打印"Hello World"，像这样的代码就不需要任何的输入参数，因此算法的输入可以是零个。因为算法是解决问题的方法，你都把问题解决了，怎么会没有输出呢？所以算法至少有一个输出。输出的形式可以是：在屏幕上打印输出、返回一个值或者返回多个值。
有穷性
有穷性：**指算法执行有限的步骤之后，自动结束而不会出现死循环，并且每个步骤在有穷的时间内完成。**但是有穷并不意味着，你写一个算法，计算机需要运行上几十年才能结束。那你要这算法又有何用呢？
确定性
确定性： 算法的每个步骤都有确定的含义，不会出现二义性。 算法在任何条件下，只有唯一一条的执行路径，相同的输入只能有唯一的输出。
可行性
可行性：算法的每一步都必须是可以的，也就是说，每一步都能通过执行有限次数完成。 可行性意味着算法能在计算机上运行，并且得到正确的结果。
3.算法设计的要求
正确性
正确性：算法的正确性是指算法至少应该具有输入、输出和加工处理无歧义性、能正确反映问题的需求、能够得到问题的正确答案。
可读性
可读性：算法设计的另一个目的是为了方便阅读、理解和交流。可读性高有助于别人了解你的算法，晦涩难懂的算法往往隐含错误，难以被发现，并且不方便调试和修改。
健壮性
健壮性：当输入的数据不合法时，算法能够对此进行处理，而不是输出异常的结果。一个好的算法应该能对输入数据不合法的情况做出合适的处理。比如输入的时间或身高为负数时，提示使用者输入大于0的数据等等。
时间效率高和存储量低
时间效率指的是算法的执行时间，而存储量需求指的是算法在执行过程中需要的最大存储空间，主要指算法运行时所占用的内存或外部硬盘的存储空间。在生活中，人们总想花最少的钱、用最短的时间，办成最大的事。算法也是一样，用最少的空间，花最少的时间，办到同样的事。所以，设计算法要精良满足时间效率高和存储量低的要求。
算法效率
1.如何衡量一个算法的好坏
如何去衡量一个算法的好坏呢？比如对于以下求斐波那契数的函数：
long long Fib(int n) { if (n <= 2) return 1; else return Fib(n - 1) + Fib(n - 1); }
斐波那契数列的递归实现方式非常简洁，但是简洁就一定好吗？那该如何衡量去好与坏呢？这就需要分析算法的时间复杂度和空间复杂度了。
2.算法的复杂度
算法在编写成可执行程序后，运行时需要消耗时间资源和夸奖资源。因此衡量一个算法的好坏，一般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。时间复杂度主要衡量一个算法的运行快慢，而空间复杂度主要衡量一个算法运行所需要的额外空间。
时间复杂度
1.时间复杂度的定义
在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。一个算法的时间复杂度不能取决于算法执行所耗费的时间。因为一个相同的算法放在不同的机器上测试，所耗费的时间就可能有很大的不同。一个算法所花费的时间与其中语句的执行次数成正比例，算法的基本操作的执行次数为算法的时间复杂度。
那一个算法的时间复杂度怎么表示呢？算法的时间复杂度用O()来表示，我们称之为大O渐进表示法。接下来，我们来一起学习一下。
2.大O渐进表示法
推导大O阶：
1.用常数1取代运行时间中的所有加法常数
2.在修改后的运行次数函数中，只保留最高阶项
3.如果最高阶项存在且不是1，则去掉与这个项相乘的常数
4.得到的结果就是大O阶
3.时间复杂度分析
平方阶O(N^2)
代码示例：
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 < 2 * N; k++) { count++; } int m = 10; while (m) { count++; m--; } printf("%d\n", count); }
很明显，Func1函数执行的基本操作次数为F(N)=N^2+2*N+10。
F(N)=N^2+2*N+10
- N=10 F(N)=130
- N=100 F(N)=10210
- N=1000 F(N)=1002010
从上面可以看出，N越大后两项对结果的影响越小的。根据大O渐进表示法，Func1函数的时间复杂度为O(N^2)。
线性阶O(N)
代码示例：
void Func2(int N) { int count = 0; for (int i = 0; i < 2 * N; i++) { count++; } int M = 10; while (M--) { count++; } printf("%d\n", count); }
很容易分析得出，Func2函数执行的基本操作次数为F(N)=2*N+10。那么根据大O渐进表示法，函数Func2的时间复杂度就是O(N)。
代码示例：
void Func3(int N,int M) { int count = 0; for (int i = 0; i < N; i++) { count++; } for (int i = 0; i < M; i++) { count++; } printf("%d\n", count); }
很明显，Func3函数的时间复杂度为O(M+N)。一般情况下，时间复杂度的未知数用的都是N，但是也可以用M、K等等字母。
M远大于N，Func3函数的时间复杂度为O(M)
N远大于M，Func3函数的时间复杂度为O(N)
M和N差不多大，Func3函数的时间复杂度为O(M)或O(N)
代码示例：
long long Fac(int N) { if (N <= 1) return 1; else return Fac(N - 1) * N; }
这是一个递归算法，那么递归算法的时间复杂度怎么计算呢？其实递归算法的时间复杂度=递归次数×每次递归调用的次数。那么Fac阶乘函数的时间复杂度就是O(N)。
常数阶O(1)
代码示例：
void Func4() { int count = 0; for (int i = 0; i < 100; i++) { count++; } printf("%d\n", count++); }
很明显，Func3函数执行的基本操作次数为100。根据大O渐进表示法，Func3函数的时间复杂度就是O(1)。注意：O(1)表示代表算法只运行一次，而是运行了常数次。
对数阶O(logN)
代码示例：
void Func5(int N) { int count = 1; while (count < N) { count *= 2; } }
假设循环x次后，count大于或等于N了，不满足循环条件。那么2^x = N，可以得到循环次数x = log2(N)。所以Func5函数的时间复杂度是O(logN)。注意：logN通常表示以2为底的对数。如果是以其他数字为底的对数，需要标注出来。
指数阶O(2^N)
代码示例：
long long Fib(int n) { if (n <= 2) return 1; else return Fib(n - 1) + Fib(n - 1); }
在算法效率的开头那里，我们提出了一个问题：斐波那契数列算法的效率如何？接下来，我们就来分析一下。因为递归算法的时间复杂度=递归次数×每次递归调用的次数，而该算法的每次递归调用的次数为O(1)，所以我们只需要算出递归次数就行了。具体分析见下图：
指数阶的算法已经是时间复杂度非常大的算法了，是不会经常使用的。所以上面斐波那契数列的求解可以使用循环的方式来实现。
#include <stdio.h> long long Fib(N) { long long a = 1; long long b = 1; long long c = 1; while (N > 2) { c = a + b; a = b; b = c; N--; } return c; } int main() { printf("%lld\n", Fib(40)); return 0; }
4.常见的时间复杂度
限于文章的篇幅，有一些时间复杂度还没有提及。在后续的文章，我们会进行讲解。
5.最好、最坏和平均情况
在上面，我们分析一些常见的时间复杂度。但是有时候，有一些算法会因为输入的不同，其时间复杂度也会不同。那么算法的时间复杂度就有了最好、最坏和平均三种情况了。
最好情况：任意输入规模的最小运行次数（下界）
平均情况：任意输入规模的期望运行次数
最坏情况：任意输入规模的最大运行次数（上界）
代码示例：
const char* strchr(const char* str, int character) { while (*str) { if (*str == character) return str; else str++; } }
从上图可以看出，随着输入的不同，查找的次数也不同。那这个算法的时间复杂度怎么算呢？注意：当一个算法随着输入的不同，时间复杂度也不同。那么时间复杂度就要做悲观预期，最坏情况的时间复杂度就是该算法的时间复杂度。所以strchr函数的时间复杂度为O(N)。 一般在没有特殊说明的情况下，时间复杂度都是值最坏时间复杂度。 最好情况和平均情况的时间复杂符不经常使用。
空间复杂度
1.空间复杂度的定义
空间复杂度也是一个数学函数表达式，是对一个算法在运行过程中临时额外占用存储空间大小的度量。
空间复杂度不是计算程序占用了多少个字节的空间，因为这个没有太大的意义，所以空间复杂度算的是变量的个数。空间复杂度的计算规则基本跟时间复杂度类似，也使用大O渐进表示法。
注意：函数运行时所需要的占空间（存储参数、局部变量、一些寄存器信息等）在编译期间已经确定好了，因此空间复杂度主要通过函数在运行时申请的额外空间来确定。
2.空间复杂度分析
分析一下代码的空间复杂度：
代码示例：
void BubbleSort(int* a, int n) { assert(a); for (size_t end = n; end > 0; --end) { int exchange = 0; for (size_t i = 1; i < end; ++i) { if (a[i - 1] > a[i]) { Swap(&a[i - 1], &a[i]); exchange = 1; } } if (exchange == 0) break; } } //空间复杂度为O(1) 时间复杂度为O(N^2)
代码示例：
//计算Fib的空间复杂度 //返回斐波那契数列的前n项 long long* Fib(int n) { if (n == 0) return NULL; long long* FibArray = (long long*)malloc((n + 1) * sizeof(long long)); FibArray[0] = 0; FibArray[1] = 1; for (int i = 2; i <= n; i++) { FibArray[i] = FibArray[i - 1] + FibArray[i - 2]; } return FibArray; }
代码示例：
long long Fac(int N) { if (N <= 1) return 1; else return Fac(N - 1) * N; }
代码示例：
long long Fib(int n) { if (n <= 2) return 1; else return Fib(n - 1) + Fib(n - 1); }
因为现在计算机的存储容量已经到了很高的程度，所以我们如今已经不需要再特别关注一个算法的空间复杂度了。因此，在大多时候，我们所写的算法会采取用时间换时间的方式。
总结
🧡 🧡 🧡在本篇博客里，主要向大家介绍了算法的定义、特性和设计要求，还重点分析了算法时间复杂度和空间复杂度。如果大家觉得有收获的话，可以点个三连支持一下！ 谢谢大家啦！！!🧡 🧡 🧡
