【数据结构入坑指南（一）】--《实战：暴力解VS最优解——一道轮转数组题引发的复杂度「血案」》
🔥@晨非辰Tong：个人主页
💪学习阶段：C语言方向初学者
⏳“人理解迭代，神理解递归。”
引言：当你还沉浸在C语言指针的余韵中时，招聘网站上的岗位要求已经写满了“熟练掌握数据结构与算法”。你是否好奇，为什么面试官总爱问“这段代码的时间复杂度是多少”？因为不懂复杂度分析，写出的程序可能就是一场效率灾难。本篇将为你揭秘如何评判代码的效率，让你从“能跑就行”进阶到“跑得飞快”。
目录
1. 基本介绍
1.1 数据结构
--是计算机存储、组织（增删查改）数据的方式，指相互之间一种或多种特定关系的数据元素的集合。没有一种单一的数据结构对所有用途都有用，所以要学习各种的数据结构：线性表、树、图、哈希...（包括数组）
1.2 算法
--简单说，算法是满足严格条件的详细的解题思路（计算步骤），将数据输入转换为结果输出。
--当然一道算法题有多种解题思路，选择哪个——>看复杂度！——>重点注意！！
1.3 重要性
--数据算法不分家，二者的考量在校园招聘频频出现，且大多位编程题（考验写代码的能力）。
--学好数据结构的方法：
- 死磕代码，代码勤练，多刷题，前期没思路？无妨，从模仿开始！
- 画图+思考，有些题经过画图动态理解运行过程，可能就有思路了。
2. 思路选择的标准——>复杂度
--先由例题引出问题：力扣_189. 轮转数组
--这是轮转一回的。
--根据这样的思路：每次都将最后一位放在临时变量中，前面的元素依次向后移动一位；如此共三次(k次)。
void rotate(int* nums, int numsSize, int k) { while(k--) { //将最后一位先放在一边 int temp = nums[numsSize - 1]; //循环进行轮换 for(int i = numsSize - 1; i > 0; i--) { nums[i] = nums[i - 1]; } //将最后一个放在最前面 nums[0] = temp; } }--但发现最后提示超出时间限制。代码本身思路没问题，那只能是运行时间太长了，效率低。涉及复杂度，来判断代码的效率。
2.1 介绍复杂度（重要，理解）
--算法编写完程序后，运行会占用时间、空间（内存），这两个元素就是衡量算法好坏的标准：时间复杂度、空间复杂度。（主要是空间维度，越小越好）
--在校招也会对复杂度进行考察！
3. 时间复杂度
--定义：时间复杂度是个函数式：T(N)，定量描述算法运行时间。（N指代所有变量）
--时间复杂度：衡量程序的时间效率（变化趋势的快慢）。
--为什么不计算运行时间？不同机器配置、编译环境，导致时间不同；时间只能在程序运行后得到，无法由理论思想评估。
--T(N)，计算了程序执行次数。C语言编译链接部分，知道算法程序编译生成二进制指令，cpu执行这些指令。
--由代码或理论思想计算T(N)，假定指令执行时间一样，那么执行次数N就占大头——>近似的，次数代表时间效率的好坏，T(N)越大，效率一定是低的。
程序运行时间 = 二进制指令运行时间 * 执行次数
（假定时间是一定的——>常量；次数是最大影响因素）
（主要看循环语句的执行次数；非循环语句只执行一次，不计算，总体影响不大。）
--例1
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^2?
由表格知：变量N是未知的，N变化时，对T(N)影响最大的是N^2，相比其他M是已知的的忽略不计。
--计算时间复杂度，只是比较增长量级。当变量N变化时，观察T(N)的变化趋势。上面看到低阶项、常数项影响很小，只用计算大概执行次数来表示变化趋势，通常使用大O的渐进表示法。
3.1 大O的渐进表示法
--大O符号：描述函数渐进行为的符号。规则：
- T(N)，只保留最高阶项，去掉低阶项；
- 若最高项存在且不为1，可以去掉项的系数；
- T(N)中若没有与N有关的项，只有常数项，用1取代所有加法常数；
--上面Func1时间复杂度：O(N^2).
3.2 时间复杂度计算(常见的时间复杂度推理，掌握方法)
--练习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); } 
--练习2：
//计算Func3的时间复杂度？ void Func3(int N, int M) { int count = 0; for (int k = 0; k < M; ++ k) { ++count; } for (int k = 0; k < N ; ++ k) { ++count; } printf("%d\n", count); }
--前面说过，N指代所有变量，直接是2N。
--练习3：
//计算Func4的时间复杂度？ void Func4(int N) { int count = 0; for (int k = 0; k < 100; ++ k) { ++count; } printf("%d\n", count); }
--练习4：
// 计算strchr的时间复杂度？ const char* strchr(const char* str, int character) { const char* p_begin = str; while (*p_begin != character) { if (*p_begin == '\0') return NULL; p_begin++; } return p_begin; }
大O的渐进表示法选择：
💡总结：发现有些时间复杂度存在最好、最坏、平均的情况
最坏：任意输入规模的最大运行次数——上界；
平均：任意输入规模的期望运行次数；
最好：任意输入规模的最小运行次数——下界；
--大O的渐进表示法关注上界
--练习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; } }
--练习6：
void func5(int n) { int cnt = 1; while (cnt < n) { cnt *= 2; } }
对数书写注意：
注意：对于对数的书写，当n接近无穷大时，底数大小对结果影响不大，可以省略。直接表示为log n。
--练习7：
// 计算阶乘递归Fac的时间复杂度？ long long Fac(size_t N) { if(0 == N) return 1; return Fac(N-1)*N; }
4. 空间复杂度
--定义：是数学表达式，描述算法在运行中除原始的输入数据所占空间外，为了运行算法而额外临时申请的空间大小。
- 不算输入数据本身：输入数据所占空间是必须的，不属于“额外开销”。
- 算大小未知的空间：算法运行过程中，函数体内临时定义的变量、数组、递归栈帧等所占空间。（一般情况可以说算的是变量的个数。）
4.1 空间复杂度计算
--练习1：一般情况
//计算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; } }
--练习2：这就要看函数栈帧空间的大小了
//计算阶乘递归Fac的空间复杂度？ long long Fac(size_t N) { if(N == 0) return 1; return Fac(N-1)*N; }
--补充:数组动态开辟内存，大小未知，O(N)。
void func(int n) { int* arr = (int*)malloc(n * sizeof(int)); } 5. 常见复杂度对比
6. 复杂度算法题
--思路一
时间复杂度O(N^2)，空间复杂度O(N^2)
--复杂度高，效率低，舍弃
void rotate(int* nums, int numsSize, int k) { while(k--) { //将最后一位先放在一边 int temp = nums[numsSize - 1]; //循环进行轮换 for(int i = numsSize - 1; i > 0; i--) { nums[i] = nums[i - 1]; } //将最后一个放在最前面 nums[0] = temp; } }--思路二
时间复杂度O(N)，空间复杂度O(N);
--比上一思路时间减少了，但空间增大。这就是常见的空间换时间。
void rotate(int* nums, int numsSize, int k) { int temp[numsSize]; for(int i = 0; i < numsSize; i++) { temp[(i+k)%numsSize] = nums[i]; } for(int i = 0; i < numsSize; i++) { nums[i] = temp[i]; } }
--思路三
时间复杂度：O(N)，空间复杂度：O(1)
void reverse(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;//防止出现k>numsSize出错 //前n-k个数据逆置 reverse(nums, 0, numsSize - 1 - k); //后k个数据逆置 reverse(nums, numsSize - k, numsSize - 1); //整体逆置 reverse(nums, 0, numsSize - 1); }
结语：复杂度分析就像我们踏入数据结构与算法世界获得的第一件“标尺”，它或许有些抽象，但却是我们未来选择最优解决方案最可靠的依据。不必为一时的不熟练而焦虑，多看、多练、多画图，这种感觉自然会变得敏锐。——本篇是「数据结构与算法」系列的开篇之作，希望能为你打下坚实的基础。接下来的旅程，我将与你一同深入更多精彩的数据结构。你的每一个点赞、评论和关注，都是我持续创作的最大动力！我们下期再见！
