空间复杂度实例

2024-07-10 09:11:05| 来源: 网络整理| 查看: 265

文章目录一、算法效率💦 如何衡量一个算法的好坏💦 算法的复杂度二、时间复杂度💦 什么是时间复杂度💦 大O渐进表示法 (估算)💦 常见的时间复杂度计算举例💦 常见的复杂度对比💦 根据对时间复杂度的要求编写代码三、空间复杂度💦什么是空间复杂度💦 常见的空间复杂度计算举例

一、算法效率 💦 如何衡量一个算法的好坏

🎗递归代码 ———— 斐波那契数列的代码量十分简洁，所以这个算法是很优的？但其实使用递归是非常戳的，你会发现递归去计算第40位斐波那契数时都要跑半天，究其原因是内部产生大量重复的计算。那该如何去衡量算法的优劣呢？

#define _CRT_SECURE_NO_WARNINGS #include int Fib(int n) { if(n > 2) return Fib(n - 1) + Fib(n - 2); else return 1; } int main() { int n = 0; scanf("%d", &n); int ret = Fib(n); printf("第%d个斐波那契数是%d\n", n, ret); return 0; } 💦 算法的复杂度算法在编写成可执行程序后，运行时需要耗费时间资源和空间(内存)资源。因此衡量一个算法的好坏，一般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。时间复杂度主要衡量一个算法的运行快慢，而空间复杂度主要衡量一个算法运行所需要的额外空间。在计算机发展的早期，计算机的存储容量很小。所以对空间复杂度比较在乎。但是经过计算机行业的迅速发展，计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注算法的空间复杂度。二、时间复杂度 💦 什么是时间复杂度在计算机科学中，算法的时间复杂度是一个函数，它描述了该算法的运行时间。一个算法执行所耗费的时间，从理论上说，是不能算出来的，只有你把你的程序放在机器上跑起来，才能知道。但是我们需要每个算法都上机测试吗?是可以上机测试，但是这很麻烦，所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比，所以算法中的基本操作的执行次数，为算法的时间复杂度。即找到某条基本语句与问题规模N之间的数学表达式，就是算出了该算法的时间复杂度。

🎗 计算fun1中++count语句总共执行了多少次

void Func1(int N) { int count = 0; for (int i = 0; i ++count; } } for (int k = 0; k ++count; } printf("%d\n", count); }

📝 分析：从上述代码中可以看出Func1的时间复杂度函数为F(N) = N * N + 2 * N + 10

▶ N = 10 F(N) = 130

▶ N = 100 F(N) = 10210

▶ N = 1000 F(N) = 1002010

💨 从上述就可以看出N越大，对结果的影响就越小。实际中我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要大概执行次数，那么这里我们使用大O的渐进表示法 (估算)。

💦 大O渐进表示法 (估算)

大O符号 (Big O notation)：用于描述函数渐近行为的数学符号

🎗推导大O阶的方法：

1️⃣ 用常数１取代运行时间中的所有加法常数

2️⃣ 在修改后的运行次数函数中，只保留最高项

3️⃣ 如果最高阶项存在且系数不是１，则去除与这个项相乘的系数，得到的结果就是大O阶

💨 对于上面的Func1函数，使用大O的渐近表示法后，时间复杂度为O(N^2)

▶ N = 10 F(N) = 100

▶ N = 100 F(N) = 10000

▶ N = 1000 F(N) = 1000000

🎗另外有些算法的时间复杂度存在最好，平均和最坏情况: 例如：在一个长度为N的数组中查找一个数据X，最好的情况1次就找到；平均的情况N/2就找到；最坏的情况N次才找到

1️⃣ 最坏情况:任意输入规模的最大运行次数(上界)

2️⃣ 平均情况:任意输入规模的期望运行次数

3️⃣ 最好情况:任意输入规模的最小运行次数(下界)

💨 在实际中一般情况关注的是算法的最坏运行情况，所以数组中搜索数据时间复杂度为O(N)

💦 常见的时间复杂度计算举例

🎗实例1:

void Func2(int N) { int count = 0; for (int k = 0; k ++count; } printf("%d\n", count); }

📝 分析： Func2的时间复杂度函数为F(N) = (2N + 10) 使用大O渐近表示法：保留影响最大的一项、去掉系数则为O(N)

🎗实例2:

void Func3(int N, int M) { int count = 0; for (int k = 0; k ++count; } printf("%d\n", count); }

📝 分析： Func3的时间复杂度函数为F(N) = (M + N) 使用大O渐近表示法：不一定只有一个未知数，所以这里可以写O(M + N) 也可以写成如下： ▶ O(ｍax(M, N))：取M和N的较大值

▶ O(M)：如果能说明M远大于N

▶ O(N)：如果能说明N远大于M

▶ O(N)/O(M)：如果能说明M和N差不多大

🎗实例3:

void Func4(int N) { int count = 0; for (int k = 0; k assert(a); for (size_t end = n; end > 0; --end) { int exchange = 0; for (size_t i = 1; i Swap(&a[i-1], &a[i]); exchange = 1; } } if (exchange == 0) break; } }

📝 分析：这是冒泡排序的一个优化版本，在一趟排序的过程中如果没有交换数据的话，它就会跳出循环，所以它是有最好、平均、最坏的情况的 BubbleSort的时间复杂度函数为F(N) = (n + (n - 1) + (n - 2) … + 2 + 1) 所以你会发现这是一个等差数列，利用公式整合得：F(N) = (n + 1)* n / 2 -> F(N) = n^2 / 2 + n / 2 使用大O渐近表示法： (最坏情况)：O(N^2) -> 这是我们要考虑的情况，显然如果是最坏的情况，那我们就优化了个寂寞 (平均情况)：O(N^2) -> (n^2 / 2 + n / 2)/2 (最好情况)：O(N)

🎗实例4:

int BinarySearch(int* a, int n, int x) { assert(a); int begin = 0; int end = n-1; while (begin if(1 == N) return 1; return Fac(N-1)*N; }

📝 分析： Fac的时间复杂度为F(N) = (N) 使用大O渐近表示法：O(N)

🎗实例6:

long long Fib(size_t N) { if(N sum += i; } //再减去数组里的数，结果就是缺失的数 for (i = 0; i int arr[20] = { 0 }; //规定输入有n个数 int n = 3; int i = 0; for (i = 0; i int i = 0; //把n+1个数异或后，放在sum里 int sum = 0; for (i = 0; i sum ^= arr[i]; } return sum; } int main() { int arr[20] = { 0 }; //n个数 int n = 3; int i = 0; for (i = 0; i assert(arr && temp); //拷贝一份新空间的首地址用于返回 char* tem = temp; //我们当前写的这个代码是不适用于旋转的字符k大于目标数组的arr，所以如果k大于arr时，我们需要看看k有几个arr,并把它排除掉 k %= len; int i = 0; //先拷贝后半部分的字符 for (i = len - k; i *temp = *(arr + i); temp++; } return tem; } int main() { //temp为新的空间 char temp[20] = { 0 }; //arr存储要旋转的字符串 char arr[20] = { 0 }; gets(arr); //旋转k个字符 int k = 0; scanf("%d", &k); char* ret = Rotate1(arr, strlen(arr), k, temp); printf("%s\n", ret); return 0; }

🎗 方法３

#define _CRT_SECURE_NO_WARNINGS #include #include #include void reverse(char* left, char* right) { assert(left && right); while (left assert(str); int len = strlen(str); //我们当前写的这个代码是不适用于旋转的字符k大于目标数组的arr，所以如果k大于arr时，我们需要看看k有几个arr,并把它排除掉 k %= len; reverse(str, str + (len - k - 1));//第一部分 reverse(str + (len - k), str + len - 1);//第二部分 reverse(str, str + len - 1);//整体 } int main() { //arr存储要旋转的字符串 char arr[20] = { 0 }; gets(arr); //旋转k个字符 int k = 0; scanf("%d", &k); string_right_rotation(arr, k); printf("%s\n", arr); return 0; } 三、空间复杂度 💦什么是空间复杂度空间复杂度也是一个数学表达式，是对一个算法在运行过程中临时占用存储空间大小的量度。空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟时间复杂度类似，也使用大o渐进表示法。注意:函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了，因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。 💦 常见的空间复杂度计算举例

相对简单，过一下即可： 🎗实例1:

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 Swap(&a[i-1], &a[i]); exchange = 1; } } if (exchange == 0) break; } }

📝 分析：相比时间复杂度来说：时间是累计的，但空间不是累计的(可以重复利用) BubbleSort的空间复杂度为F(N) = (３) 使用大O渐近表示法：O(１)

🎗实例2:

long long* Fibonacci(size_t n) { if(n==0) return NULL; long long * fibArray = (long long *)malloc((n+1) * sizeof(long long)); fibArray[0] = 0; fibArray[1] = 1; for (int i = 2; i if(N == 1) return 1; return Fac(N-1)*N; }

📝 分析：使用大O渐近表示法：O(N)

🎗实例1:

long long Fib(size_t N) { if(N

【本文地址】

公司简介

联系我们

今日新闻

点击排行

实验室常用的仪器、试剂和: 说到实验室常用到的东西，主要就分为仪器、试剂和耗

不用再找了，全球10大实验: 01、赛默飞世尔科技（热电）Thermo Fisher Scientif

三代水柜的量产巅峰T-72坦: 作者：寞寒最近，西边闹腾挺大，本来小寞以为忙完这

通风柜跟实验室通风系统有: 说到通风柜跟实验室通风，不少人都纠结二者到底是不

集消毒杀菌、烘干收纳为一: 厨房是家里细菌较多的地方，潮湿的环境、没有完全密

实验室设备之全钢实验台如: 全钢实验台是实验室家具中较为重要的家具之一，很多

图片新闻

实验室药品柜的特性有哪些: 实验室药品柜是实验室家具的重要组成部分之一，主要

小学科学实验中有哪些教学: 计算机计算器一般打孔器打气筒仪器车显微镜

实验室各种仪器原理动图讲: 1.紫外分光光谱UV分析原理：吸收紫外光能量，引起分

高中化学常见仪器及实验装: 1、可加热仪器：2、计量仪器：（1）仪器A的名称：量

微生物操作主要设备和器具: 今天盘点一下微生物操作主要设备和器具，别嫌我啰嗦

浅谈通风柜使用基本常识: 　众所周知，通风柜功能中最主要的就是排气功能。在

空间复杂度实例

空间复杂度实例

今日新闻

点击排行

推荐新闻

图片新闻

专题文章