【10月更文挑战第20天】
数据是杂乱无章的，我们要借助结构将数据管理起来
1.1 数据结构
数据结构(Data Structure)是计算机存储、组织数据的⽅式，指相互之间存在⼀种或多种特定关系的数
据元素的集合。没有⼀种单⼀的数据结构对所有⽤途都有⽤，所以我们要学各式各样的数据结构，
如：线性表、树、图、哈希等
1.2 算法
算法(Algorithm):就是定义良好的计算过程，他取⼀个或⼀组的值为输⼊，并产⽣出⼀个或⼀组值作为输出。简单来说算法就是⼀系列的计算步骤，⽤来将输⼊数据转化成输出结果。
好的算法能帮助我们更好的管理数据
数据结构是一种载体存储数据
算法是一种方法，管理数据
数据结构与算法不分家
学好数据结构可以提升面试和笔试
评估算法的好坏我们从复杂度进行评估
/*给定一个整数数组 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]
提示：
1 <= nums.length <= 105
-231 <= nums[i] <= 231 - 1
0 <= k <= 105
进阶：
尽可能想出更多的解决方案，至少有 三种 不同的方法可以解决这个问题。
你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？*/
void rotate(int* nums, int numsSize, int k)
{
while(k--)
{
int end=nums[numsSize-1];//创建一个临时变量将数组中最后一个数的值进行保存
for(int i=numsSize-1;i>0;i--)//将数组中的数整体右移一位
{
nums[i]=nums[i-1];//在右移的时候我们要从后向前移，我们现将倒数第二个数赋值到最后一个数的位置上，然后随着i的变化进行右移操作
}
nums[0]=end;//最后我们将之前保存的值放到以一个位置上
}
}
//但是这个存在限制，虽然这个代码没有问题，算法虽然没问题，但是超过时间限制，一但遇到大的数据，时间就变长了
第一种方法虽然算法是对的，但是一但遇到大的数据就计算不过来，计算时间很长
那么就衍生出了算法好坏的概念：算法复杂度
我们通过算法复杂度去衡量算法的好坏
复杂度分为时间复杂度和空间复杂度
算法在编写成可执⾏程序后，运⾏时需要耗费时间资源和空间(内存)资源 。因此衡量⼀个算法的好坏，⼀般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。
时间复杂度主要衡量⼀个算法的运⾏快慢，⽽空间复杂度主要衡量⼀个算法运⾏所需要的额外空间。在计算机发展的早期，计算机的存储容量很⼩。所以对空间复杂度很是在乎。但是经过计算机⾏业的迅速发展，计算机的存储容量已经达到了很⾼的程度。所以我们如今已经不需要再特别关注⼀个算法的空间复杂度
时间复杂度铺垫
定义：在计算机科学中，算法的时间复杂度是⼀个函数式T(N)，它定量描述了该算法的运⾏时间。时间复杂度是衡量程序的时间效率，
int main()
{
//计算程序运行时间
//计算时间我们要用到库time.h里的clock（）
//可以记录在不同时间段的时间
//我们记录开始和结束的时间，就得到了程序运行的时间
int begin=clock();//定义起始时间
int count = 0;
for (int i = 0; i < 100000000; i++)
{
count++;
}
int end = clock();//定义结束时间
//那么
printf("time:%d", end - begin);//当前算法运行时间
//得到的结果是0毫秒啊，如果我们给上一个亿的范围得到的就是59
// 这个时间不是一个确切的时间
//使用debug模式会加载一些调试信息，会占用一些我们程序的运行时间
return 0;
}
//因为程序运行的时间不是一个确切的数，所以我们时间复杂度不能给出一个确切的数字
时间复杂度是衡量程序的时间效率，那么为什么不去计算程序的运⾏时间呢？
因为程序运⾏时间和编译环境和运⾏机器的配置都有关系，⽐如同⼀个算法程序，⽤⼀个⽼编译器进⾏编译和新编译器编译，在同样机器下运⾏时间不同。
同⼀个算法程序，⽤⼀个⽼低配置机器和新⾼配置机器，运⾏时间也不同。
并且时间只能程序写好后测试，不能写程序前通过理论思想计算评估。
因为程序运行的时间不是一个确切的数，所以我们时间复杂度不能给出一个确切的数字
我希望时间复杂度在编写算法之前就知道的，这个运行时间只能在程序编写好之后进行测试，不能在编写前计算评估
所以复杂度不是一个精确的数字，是一个粗估的数字
int main()
{
int count = 0;//运行1次
for (int i = 0; i < 100000000; i++)
{
count++;//运行了100000000次
}
int end = clock();
return 0;
}
//那么运行次数是100000001次
程序效率：每条语句运行时间 * 次数
这个运行时间和编译环境和运行环境相关的，这个时间是不确定的，但是运行次数我们是能确定的
随着这个运行次数的增加，运行时间是正相关的，所以我们在计算时间复杂度的时候可以直接根据运行次数进行确定
// 请计算⼀下Func1中++count语句总共执⾏了多少次？
void Func1(int N)
{
int count = 0;
//这个for循环执行的次数就是N*N
for (int i = 0; i < N; ++i)
{
for (int j = 0; j < N; ++j)
{
++count;
}
}
//这个for循环执行的次数就是2*N
for (int k = 0; k < 2 * N; ++k)
{
++count;
}
int M = 10;
//执行次数是10
while (M--)
{
++count;
}
}
//那么我们判断的这个题的时间复杂度是T(N)=N^2+2N+10
//因为int count =0和int M=10的执行次数都是1，我们可以忽略不计的，对总的时间复杂度影响不大的
//T(N)=N^2+2N+10
//对于这个算术式，N^2的影响最大，2N+10对当前复杂度影响较小，是可以忽略不计的
//
//那么我们就能得出T(N)=N^2
//可以得出时间复杂度是粗估，但是时间复杂度不是这么写的，我们要用上大O的渐进表示法
//O(n^2)就是这个题的时间复杂度了
O(n^2)就是这个题的时间复杂度了
实际中我们计算时间复杂度时，计算的也不是程序的精确的执⾏次数，精确执⾏次数计算起来还是很⿇烦的(不同的⼀句程序代码，编译出的指令条数都是不⼀样的)，计算出精确的执⾏次数意义也不⼤，因为我么计算时间复杂度只是想⽐较算法程序的增⻓量级，也就是当N不断变⼤时T(N)的差别，上⾯我们已经看到了当N不断变⼤时常数和低阶项对结果的影响很⼩，所以我们只需要计算程序能代表增⻓量级的⼤概执⾏次数，复杂度的表⽰通常使⽤⼤O的渐进表⽰法。
⼤O的渐进表⽰法
⼤O符号（Big O notation）：是⽤于描述函数渐进⾏为的数学符号
推导大O阶规则
1.时间复杂度函数式T(N)中，只保留最高阶项，去掉那些低阶项，因为当N不断变大时，低阶项对结果影响越来越小，当N无穷大时，就可以忽略不计了。
2.如果最高阶项存在且不是1，则去除这个项目的常数系数，因为当N不断变大，这个系数2对结果影响越来越小，当N无穷大时，就可以忽略不计了。
3.T(N)中如果没有N相关的项目，只有常数项，用常数1取代所有加法常数。
时间复杂度示例
// 计算Func2的时间复杂度？
void Func2(int N)
{
int count = 0;//次数是1，忽略不计
//次数是2N
for (int k = 0; k < 2 * N; ++k)
{
++count;
}
int M = 10;
//次数是10
while (M--)
{
++count;
}
printf("%d\n", count);
}
//那么这个题我们觉得的时间复杂度是O(2N)
//但是实际确实O(N),因为这里的倍数对我们的时间复杂度影响不是很大
那么这个题就对应上了规则2
// 计算Func3的时间复杂度？
void Func3(int N, int M)
{
int count = 0;
//执行了M次
for (int k = 0; k < M; ++k)
{
++count;
}
//执行了N次
for (int k = 0; k < N; ++k)
{
++count;
}
printf("%d\n", count);
}
//那么我们就得到了时间复杂度的函数式：T(N)=M+N
//M和N都是执行次数，都是变量，都会影响到时间复杂度的结果
//那么这个题的时间复杂度就是O(M+N)
//如果说M和N中有一个较大的项，那我们就保留高阶项
//如果M>>N的话，那么这里的时间复杂度就是O(M)
//如果M<<N的话，那么这里的时间复杂度就是O(N)
//如果M大约等于N的话，那么在时间复杂度里面就都保留
// 计算Func4的时间复杂度？
void Func4(int N)
{
int count = 0;
for (int k = 0; k < 100; ++k)
{
++count;
}
printf("%d\n", count);
}
//执行的次数是100，那么得出的函数式是T(N)=100
//那么我们的时间复杂度就是O(1)
//这里的1不是运行一次，而是代表所有的常数，可以说这个是一个表示法
//计算strchr的时间复杂度？ 字符串的查找
const char* strchr(const char* str, int character)
{
const char* p_begin = s;
while (*p_begin != character)
{
if(*p_begin == '\0')
return NULL;
p_begin++;
}
return p_begin;
}
/*
T(N)取决于字符的长度N以及查找的位置
如果我们找了几次就找到了，那么这个时间复杂度就是O(1)
但是我们如果找到最后字符的时候才找到或者没有找到，那么我们这个时间复杂度就是O(N)
如果查找位置在中间的话，那么时间复杂度就是O(N/2)
所以这个题的时间复杂度取决于这个字符串的长度和查找的位置
但是对于这种有多个选项的时间复杂度呢，我们应该选择哪个作为时间复杂度呢？
O(1)是最好的情况
O(N)是最坏的情况
O(N/2)是平均的情况
*/
通过上⾯我们会发现，有些算法的时间复杂度存在最好、平均和最坏情况。
最坏情况：任意输⼊规模的最⼤运⾏次数(上界)
平均情况：任意输⼊规模的期望运⾏次数
最好情况：任意输⼊规模的最⼩运⾏次数(下界)
⼤O的渐进表⽰法在实际中⼀般情况关注的是算法的上界，也就是最坏运⾏情况
那么对于这个题来说，我们应该关注最差的情况，那么这个题的时间复杂度就是O(N)
// 计算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次，因为数组有序，就只执行N次，那么时间复杂度就是O(N)
//
//外层循环执行第一次的时候，内层循环执行N次，因为不是有序的，所以我们外层循要执行N次
/*
外1 2 3 ........n
内n-1 n-2 0
那么次数就是n-1+n-2+n-3+...+1
就是等差数列求和(n-1+1)*(n-1)/2
在这个结果中对结果影响最大的是N^2,所以这个代码的时间复杂度就是O(N^2)
*/
冒泡排序的时间复杂度为O(N^2)
void func5(int n)
{
int cnt = 1;
while (cnt < n)
{
cnt *= 2;
}
}
/*
* 当N为10的时候，我们循环4次就停止了
* 假设执行的次数为x，那么2^x=n
* 那么x就等于log2 n ,
*
* 所以这里的时间复杂度是O(log2 n)
*/
注意课件中和书籍中 log2 n 、 log n 、 lg n 的表⽰
当n接近⽆穷⼤时，底数的⼤⼩对结果影响不⼤。因此，⼀般情况下不管底数是多少都可以省略不写，即可以表⽰为 log n
不同书籍的表⽰⽅式不同，以上写法差别不⼤，我们建议使⽤ log n
对于计算机来说，这个底数的大小可以忽略不计的，因为影响很小
键盘是无法输入底数的
// 计算阶乘递归Fac的时间复杂度？
long long Fac(size_t N)
{
if (0 == N)
return 1;
return Fac(N - 1) * N;
}
/*
递归的时间复杂度是多少呢
每次递归的时间复杂度是O(1)
总共有n个O(1),那么时间复杂度就是O(N)
*/
