目录
1. 数据结构前言
1.1 数据结构
数据结构（Data Structure）是计算机储存、组织数据的方式，指相互之间存在一种或多种特定关系的数据元素的集合。没有一种单一的数据结构对所有用途都有用，所以我们要学习各种各样的数据结构。如：线性表、树、图、哈希等。
我们之前其实已经接触过数据结构了：数组。我们把散乱的数据整理在一个数组中统一管理，这就是组织数据，无非就是增删查改这四个字。但是其中蕴含的知识量却大的惊人。
1.2 算法
算法（Algorithm）：就是定义良好的计算过程，他取一个或一组的值为输入，并产生出一个或一组值作为输出。简单的来说算法就是一系列的计算步骤，用来将输入数据转换成输出结果。
其实数据结构和算法是不分家的，因为我们在使用算法的时候把数据进行输入，然后通过算法输出，而这时数据的好坏就会影响算法的效率，你们说对不对，就拿我们高中的几何题为例，选中好的数据是可以将计算过程大大简化的。
2. 算法效率
如何衡量一个算法的好坏呢？
我们来看一个案例：
给定一个整数数组
nums，将数组中的元素向右轮转k个位置，其中k是非负数。示例 1:
输入: nums = [1,2,3,4,5,6,7], k = 3 输出:[5,6,7,1,2,3,4]解释: 向右轮转 1 步:[7,1,2,3,4,5,6]向右轮转 2 步:[6,7,1,2,3,4,5]向右轮转 3 步:[5,6,7,1,2,3,4]示例 2：
输入：nums = [-1,-100,3,99], k = 2 输出：[3,99,-1,-100] 解释: 向右轮转 1 步: [99,-1,-100,3] 向右轮转 2 步: [3,99,-1,-100]
看到这个问题，我们先来想一想该怎么做。我们用画图的方式来明确我们的思路。
从画图中我们不难看出，我们要给一个变量来存储数组中最后一个元素，其余元素挨个向后走。最后把最后一个元素放入第一个元素的位置。这是我们的首要思路。现在我们写一下实现逻辑：
void rotate(int* nums, int numsSize, int k) {
while(k--)
{
int i = 0;
int temp = nums[numsSize - 1];
for(i = numsSize - 1; i > 0; i--)
{
nums[i] = nums[i - 1];
}
nums[0] = temp;
}
}我们写好了代码，现在进行自测运行：
我们自测运行是通过的，现在我们提交到远程服务器进行检测。
看起来是没有通过，这是为什么呢？该如何衡量代码的好坏呢？
2.1 复杂度的概念
算法在编写成可执行程序后，运行时需要耗费时间资源和空间（内存）资源。因此衡量一个算法的好坏，一般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。
时间复杂度主要衡量一个算法的运行快慢，而空间复杂度主要衡量一个算法运行所需要的额外空间。在计算机发展的早期计算机的储存容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展，计算机的储存容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。
2.2 时间复杂度
定义：在计算机科学中，算法的时间复杂度是一个函数式T(N)，它定量的描述了该算法的运行时间。时间复杂度是衡量程序的时间的效率，为什么不去计算程序的运行时间呢？
- 因为程序运行时间和编译环境和运行机器的配置都有关系，比如同一个算法程序，用一个老编译器进行编译和新编译器编译，在同样机器下运行时间不同。
- 同一个算法程序，用一个老低配置机器和新高配置机器，运行时间也不同。
- 同时时间只能程序写好后运行测试，不能写程序前通过理论思想计算评估。
那么这个函数式到底是什么？我们之前学过编译和链接，知道算法程序被编译后生成二进制指令，程序运行后，CPU就执行编译好的这些指令。有了这样的了解，我们来看一个案例：
计算下面这段代码的时间复杂度。
// 计算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 < 2 * N; k++)
{
++count;
}
int M = 10;
while (M--)
{
++count;
}
}我们现在来分析一下：
经过分析我们得出了函数表达式如上图。
当我们选取的N值无穷大的时候，后面俩项对结果的影响可以说是微乎其微。也就是说，我们在计算时间复杂度的时候就是可以计算量级，不必在意具体执行了多少次，只需要大概，我们可以使用大O的渐进表示方法。
3. 大O渐进表示法
大O符号：用于描述函数渐进行为的表示符号。
- 时间复杂度函数式T(N)中，只保留高阶项。去掉那些低阶项，因为当N不断变大的时候，低阶项对结果的影响越来越小，当N接近无穷的时候，就可以忽略不计了。
- 如果最高阶项存在且不是1，则去除这个项目的常数系数，因为当N不断变大时，这个系数对结果的影响越来越小，当N无穷大时，就可以忽略了。
- T(N)中如果没有与N相关的项目，只有常数项，就计为1。
我们通过上面的方法就可以计算出Func的时间复杂度：O(N^2)。
3.1 时间复杂度的计算案例
我们有了这个法则，我们来看一些例题。
3.1.1 示例1
// 计算Func2的时间复杂度
void Func2(int N)
{
int count = 0;
for (int k = 0; k < 2 * N; ++k)
{
++count;
}
int M = 10;
while (M--)
{
++count;
}
printf("%d\n", count);
}
我们可以得出时间复杂度函数式T(N)，然后通过大O渐进法得出时间复杂度为O(N)
3.1.2 示例2
// 计算Func3的时间复杂度
void Func3(int N, int M)
{
int count = 0;
for (int k = 0; k < N; ++k)
{
++count;
}
for (int k = 0; k < M; ++k)
{
++count;
}
printf("%d\n", count);
}
3.1.3 示例3
// 计算Func4的时间复杂度
void Func4(int N)
{
int count = 0;
for (int k = 0; k < 100; ++k)
{
++count;
}
printf("%d\n", count);
}
3.1.4 示例4
// 计算strchr的时间复杂度
const char* strchr(const char* str, int character)
{
const char* p_begin = str;
while (*p_begin != character)
{
if (*p_begin != character)
{
if (*p_begin == '\0')
return NULL;
p_begin++;
}
}
return p_begin;
}
总结
算法的时间复杂度存在最好、最坏、以及平均的情况。
最坏：达到最大运行次数 -- 上界
平均：期望运行次数
最好：最小运行次数 -- 下界
大O的渐进表示法是在实际中一般情况关注的是算法的上界，也就是最坏的运行情况，所以上面这个例子的时间复杂度为O(N)
3.1.5 示例5
// 计算BubbleSort的时间复杂度
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;
}
}
这里的N^2是我们计算出来的，也就意味着不是一出现多层循环时间复杂度就是O(N^)
3.1.6 示例6
void Func5(int n)
{
int cnt = 1;
while (cnt < n)
{
cnt *= 2;
}
}
3.1.7 示例7
long long Fac(size_t N)
{
if (0 == N)
return 1;
return Fac(N - 1) * N;
}
所以时间复杂度为O(N)
我们在工作时有这些时间复杂度就可以了，没有必要专门去深究这个点。空间复杂度也是一样的，没必要深究。
4. 空间复杂度
空间复杂度也是一个数学表达式，对一个算法在运行过程中因为算法的需要额外临时开辟的空间。
空间复杂度不是程序占用了多少bytes的空间，因为常规情况每个对象的大小差异不会很大，所以空间复杂度算的是变量的个数。
空间复杂度计算规则基本跟时间复杂度类似，也使用大O渐进表示法。
对于这个概念我呢不做过多的说明，基本上是一眼明了的，对于简单函数来说。至于较复杂的目前水平也是接触不到的。
5. 复杂度算法题
现在我们有了上面的知识，再返回第2节看那个算法题，为何会不通过，怎们才让它通过？
思路2：用空间换时间
我们之前写的代码放在下面：
void rotate(int* nums, int numsSize, int k) {
while(k--)
{
int i = 0;
int temp = nums[numsSize - 1];
for(i = numsSize - 1; i > 0; i--)
{
nums[i] = nums[i - 1];
}
nums[0] = temp;
}
}我们来计算一下这段代码的复杂度 -- 当k == numsSize的时候，O(N^2)
我们创建一个临时数组tem用来储存原数组轮转后的数据，然后把临时数组的值赋给原数组。
void rotate(int* nums, int numsSize, int k) {
// 创建一个临时数组tem
int tem[numsSize];
// 将原数组轮转后放入tem
for (int i = 0; i < numsSize; ++i)
{
tem[(k+i) % numsSize] = nums[i];
}
for (int i = 0; i < numsSize; ++i)
{
nums[i] = tem[i];
}
}
这里我们通过了，但是利用了空间，增加了空间的大小，换来了时间上的减少，同时时间复杂度为：O(N)。
现在加大难度，我们想要时间复杂度为O(N)空间复杂度为O(1)
思路三：三次逆置
void my_reserve(int* nums, int left, int right)
{
while(left < right)
{
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
left++;
right--;
}
}
void rotate(int* nums, int numsSize, int k) {
k = k % numsSize;
// 逆置前 numsSize - k个元素
my_reserve(nums, 0, numsSize -1- k);
// 逆置后k个数据
my_reserve(nums,numsSize - k, numsSize-1);
// 全部逆置
my_reserve(nums,0,numsSize-1);
}三次逆置就可以实现数据的轮转。