前言
这是我学习数据结构的第一份笔记，有关复杂度的知识。后期我会继续将数据结构知识的笔记补全。
数据结构含义
1. 通过数据结构，有利于把杂乱无章的数据，进行管理操作。
2. 数据结构有很多种，例如：数组等。
#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> int main() { int a = 1;//直接赋值给变量 int arr[1000]; arr[0] = 55;//通过数组这种数据结构，从而对数组里面的变量进行赋值 }
算法的含义
1. 通过一系列的计算步骤，将输入的数据转化成结果。
复杂度
复杂度的含义
1. 复杂度用来衡量一个算法的好坏。
2. 复杂度分为时间复杂度和空间复杂度。
3. 时间复杂度（主要）：算法运行的快慢。
4. 空间复杂度：算法运行所需要的额外空间。
时间复杂度
可以表示为一个函数式：T(N) 。
计算时间复杂度的公式
1. n：程序运行时间效率。
2. a：每条语句的运行时间（注：a不是一个确定的值，与编译环境有关。）
3. b：每条语句的运行次数（注：b是一个确定的值。）
计算程序运行时间
#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <time.h> int main() { int begin=clock();//记录程序刚开始的时间 int count = 0; for (int i = 0; i < 10000000; i++) { count++; } int end = clock();//记录程序刚结束的时间 printf("%d", end - begin);//需要在debug模式下 return 0; } //多运行几次都不同，没有精确值
大O的渐进表示法
1. 大O符号：用于描述函数渐进行为的符号。例如：O（N^2）
2. 我们通过大O的渐进表示法，来计算运行的次数。
3. 大O的渐进表示法的规则：
- 只看最高阶项。
- 如果存在最高阶项，则忽略其系数和其他常数项。
- 如果只有常数项，则直接视为1。
- 重点看循环或递归次数。
#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <time.h> void Func1(int N) { int count = 0; // 第一个循环：N * N 次迭代 for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { ++count; } } // 第二个循环：2 * N 次迭代 for (int k = 0; k < 2 * N; ++k) { ++count; } // while 循环：10 次迭代 int M = 10; while (M--) { ++count; } } //T(N)=N^2+2N+10 //复杂度为:O(N^2)
void Func2(int N) { int count = 0; // 这个循环将执行 2 * N 次 for (int k = 0; k < 2 * N; ++k) { ++count; } // 这个循环将执行 10 次 int M = 10; while (M--) { ++count; } printf("%d\n", count); } //T(N)=2*N+10 //复杂度为：O(N)
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 //复杂度为：O(M+N)
void Func4(int N) { int count = 0; // 这个循环将执行 100 次 for (int k = 0; k < 100; ++k) { ++count; } printf("%d\n", count); } //T(N)=100 //复杂度为: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; } //上界：最坏的情况O(N)，若要查找的字符在字符串第⼀个位置。 //下界：最好的情况O(1)，若要查找的字符在字符串最后的⼀个位置。 //主要关注上界最差的情况
#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #define N int main() { int arr[N] = { 0 }; int i = 0; for (i = 0; i < N; i++) { scanf("%d", &arr[i]); } int a = 0, b = 0; for (a = 0; a < N-1; a++) { for (b = 0 ; b < N-1-a; b++) { if (arr[b] > arr[b + 1]) { int mid = 0; mid = arr[b + 1]; arr[b + 1] = arr[b]; arr[b] = mid; } } } for (i = 0; i < N; i++) { printf("%d\n", arr[i]); } return 0; } //T(N)=N(N-1)/2 //复杂度为:O(N^2)
void func5(int n) { int cnt = 1; while (cnt < N) { cnt *= 2; } } //T(N)=log（N）,不管底数。
long long Fac(size_t N) { if (0 == N) { return 1; } return Fac(N - 1) * N; } //T(N)=N //复杂度为:O(N)
上下界
最坏情况：任意输⼊规模的最⼤运⾏次数(上界)
平均情况：任意输⼊规模的期望运⾏次数
最好情况：任意输⼊规模的最⼩运⾏次数(下界)
空间复杂度
计算空间复杂度
1. 专指函数在运行时所额外占用的空间。
2. 规则与时间复杂度相同。
3. 重点看定义的变量个数。
void BubbleSort(int* a, int n) { assert(a); for (size_t end = n; end > 0; --end) //第一个end { int exchange = 0;//第二个exchange for (size_t i = 1; i < end; ++i) //第三个i { if (a[i - 1] > a[i]) { Swap(&a[i - 1], &a[i]); exchange = 1; } } if (exchange == 0) break; } } //空间复杂度为:O(1)
long long Fac(size_t N) { if (N == 0) return 1; return Fac(N - 1) * N;//第一个Fac(N - 1) * N } //空间复杂度为:O(N)，每一次递归，空间复杂度增加一次。
复杂度的大小
总结
若在算法题型中，如果时间复杂度超过要求，则可以提高空间复杂度来降低时间复杂度。
例题：轮转数组
将一个数组的元素向后移k位。
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]; } nums[0] = end; } } //通过两个内外层循环从而达到目标 改进后： void rotate(int* nums, int numsSize, int k) { int newArr[numsSize]; for (int i = 0; i < numsSize; ++i) { newArr[(i + k) % numsSize] = nums[i]; } for (int i = 0; i < numsSize; ++i) { nums[i] = newArr[i]; } } //通过创建一个新的数组从而达到目标
致谢
感谢您花时间阅读这篇文章！如果您对本文有任何疑问、建议或是想要分享您的看法，请不要犹豫，在评论区留下您的宝贵意见。每一次互动都是我前进的动力，您的支持是我最大的鼓励。期待与您的交流，让我们共同成长，探索技术世界的无限可能！
