黑群晖 DSM 7.2 旧电脑部署：3步完成引导盘制作与局域网访问
2026/7/6 11:59:28
一.什么是数据结构
数据结构(Data Structure)是计算机存储、组织数据的方式，指相互之间存在⼀种或多种特定关系的数据集合。
不存在一种通用的数据结构针对于所有应用场景，所以产生了多种多样的数据结构来适配不同的环境：例如顺序表、链表、堆栈、二叉树、队列等
二.算法
算法(Algorithim)是定义良好的计算过程，指的是针对一个或一组输出，经过该算法后，产生一个或着多个输出的中间过程。而评判算法优劣的其中一个因素就是时间复杂度和空间复杂度
以力扣189旋转数组为例：
给定了一个需要右旋的数组以及右旋的次数，最简单的方法即是将最后一个下标的元素取出放入中间变量tmp，其余元素依次右移一个下标，共循环k次即可。根据思路写出代码：
void rotate(int* nums, int numsSize, int k) {
int i =0;
for(i=0;i<k;i++)//每次往右挪一个数，循环k次。
{
int tmp = nums[numsSize-1];
int j = 0;
for(j=numsSize-1;j>0;j--)
{
nums[j]=nums[j-1];
}
nums[0]=tmp;
}
}
运行可以发现两个测试用例可以通过，但是提交却发现：
检查代码发现没有出现死循环的情况 ，那应该确实是代码运行时间超出了系统规定的时间。
根据此案例，引出今天的主题——时间复杂度和空间复杂度
三.复杂度
在代码写好后，运行则需要消耗时间资源和空间(内存)资源，因此衡量一个算法的好坏是根据时间和空间来衡量的
3.1时间复杂度
在计算机科学中，定义时间复杂度为函数式T(N)。它描述的是算法的运行时间随变量不同而发生变化的一种趋势，它并不是实际的运行时间，而是一种趋势。要理解清楚它不是具体的某个值，而是一种趋势。
首先提出表示时间复杂度的方法，然后根据具体案例分析如何应用这个方法计算时间复杂度：
表示时间复杂度的方法为：大O渐进法。
其具体规则为：
1.时间复杂度函数式T(N)中，只保留最高阶项，去掉那些低阶项，因为当N不断变大时，
低阶项对结果影响越来越⼩，当N无穷大时，就可以忽略不计了。
2.如果最⾼阶项存在且不是1，则去除这个项⽬的常数系数，因为当N不断变⼤，这个系数
对结果影响越来越小，当N无穷大时，就可以忽略不计了。
3.T(N)中如果没有N相关的项⽬，只有常数项，用常数1取代所有加法常数。
接下来结合具体代码案例，并应用上述的三个规则来计算时间复杂度
void Func1(int N)
{
int count = 0;
for (int k = 0; k < 2 * N ; ++ k)
{
++count;
}
int M = 10;
while (M--)
{
++count;
}
printf("%d\n", count);
}
首先看这个代码的for循环中出现了变量N，while循环中虽然也出现了变量M，但其为定值，循环10次，大致可以写为O(N+10)，而根据第一条规则，只保留高阶项，最后答案是O(N)。
再来看第二个例子：
void Func2(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和M，又进行了两个for循环，分别循环N次和M次，所以其时间复杂度为O(M+N)；如果M>>N，N就可以忽略不计，O(M)；同理如果N>>M，M忽略不计，O(N)。
void Func3(int N) {
int count = 0;
for (int k = 0; k < 100; ++k) {
++count;
}
printf("%d\n", count);
}
在Fun3这个函数例子中，并没有出现关于N变量的循环等操作，所以其时间复杂度为一个常数，而对于常数，根据第三条规则将其写作O(1)。
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;
}
对于strchr这个函数，仔细观看出现的while循环则会发现，它的时间复杂度取决于这个while循环，而while循环中似乎不是一个可以明确说出循环多少次的变量，是根据要查找的character有关。运气好的话，第一个是，时间复杂度为O(1)；运气不好的话，最后一个是，其时间复杂度为字符串的长度，O(N)；但 O(N)也就是最坏的情况了，如果最坏情怀下都能满足要求，那其它情况肯定能满足要求。所以对于分类讨论的情况，就按照最坏的情况。
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次：(内层)循环x次 。 第一次：n-1；第二次：n-2；第三次：n-3； ------第n-1次：1 。把总循环次数加起来则为：
可看出是等差数列，求和则为 ：，根据大O渐进法第二条规则，时间复杂度为O(N^2)。
void func5(int n) {
int cnt = 1;
while (cnt < n) {
cnt *= 2;
}
}
fun5这段代码较为简单，while循环的终止条件是<n，内部则为每次×2，相当于数出来需要2的多少次相乘就会大于n，其实就是，对数函数的形式。
而当n接近无穷大时，对数函数的底数对于其影响并不大，所以在表示时间复杂度时，都将其统一写成。
long long Fac(size_t N) {
if (N == 0)
return 1;
return Fac(N - 1) * N;
}
最后考虑到递归的情况，递归的时间复杂度= 单次时间复杂度*递归次数。对于上述阶乘递归，单次时间复杂度为1，共递归n次，最后时间复杂度为O(n)。
3.2空间复杂度
空间复杂度的定义为在一个运算执行的过程中，有多少额外开辟的空间。计算规则也是大O渐进法的三条规。
函数运⾏时所需要的栈空间(存储参数、局部变量、⼀些寄存器信息等)在编译期间已经确定好
了，因 此空间复杂度主要通过函数在运⾏时候显式申请的额外空间来确定。
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;
}
}
例如这段代码 ，在函数运行过程中，额外开辟的空间只有int exchange 和size_t 为常数，所以空间复杂度为O(1)。
而对于fun5的递归来说，空间复杂度 = 单次运行的空间复杂度* 递归次数，单次递归的空间复杂度为O(1)，共有n次，所以总的空间复杂度为O(N);
下述是两张常见复杂度的图
再次回到开头的题目实例，如果用依次向后移动的方法，其时间复杂度为O(N^2)，而题目中提供的元素个数最多为10^5，总时间为10^10ms相当于10^7s，会超过时间限制。
下述提供两种可通过的解题思路
1.
void rotate(int* nums, int numsSize, int k) {
// 把创建一个新数组，把要取下来的数放到新数组里，排好后，整体放入原数组
int arr[numsSize];
int i =0;
for(i=0;i<numsSize;i++)
{
arr[(i+k)%numsSize] = nums[i];
}
for(i=0;i<numsSize;i++)
{
nums[i]=arr[i];
}
}
整体思路为创建一个新数组，将需要移动的元素放入数组的相应位置，然后整体将原数组替换。
2.
void rotate(int* nums, int numsSize, int k) {
// 分段旋转，整体逆序
if (k > numsSize)
k %= numsSize;
int left = numsSize - k;
int right = numsSize - 1;
while (left < right) {
int tmp = nums[left];
nums[left] = nums[right];
nums[right] = tmp;
left++;
right--;
}
left = 0;
right = numsSize - 1 - k;
while (left < right) {
int tmp = nums[left];
nums[left] = nums[right];
nums[right] = tmp;
left++;
right--;
}
left = 0;
right = numsSize - 1;
while (left < right) {
int tmp = nums[left];
nums[left] = nums[right];
nums[right] = tmp;
left++;
right--;
}
}
这个思路为将最后k个需要移动的元素进行逆序，剩下的元素逆序，然后整体逆序 。