uchar范围（uchar char）



空间复杂度计算规则基本跟实践复杂度类似，也使⽤⼤O渐进表⽰法。

注意：函数运⾏时所需要的栈空间(存储参数、局部变量、⼀些寄存器信息等)在编译期间已经确定好了，因此空间复杂度主要通过函数在运⾏时候显式申请的额外空间来确定

三个变量，那么这个空间复杂度就是O(3)

https://leetcode.cn/problems/rotate-array/description/

首先将最后一位数进行保存，再将剩下的数字往右移一位，然后再将保存的数放到第一位

但是这个题有时间的限制，一但给到了一个很大的数字，那么就要消耗很多的时间，就不满足题目要求了 将numsSize看作是N

这个代码的外层循环是k，内层循环是N-1,那么时间复杂度就是O(K*N),其实可以将K看做是N，都是变量，没啥区别，那么时间复杂度就是O(N^2)，这个时间复杂度效率很低，所以在提交的时候我们会遇到超出时间限制的错误

既然这里的时间复杂度是O(N^2),空间复杂度是O(1)

那我们能不能先办法将时间复杂度降到O(N)呢？

申请一个新数组，数组大小为numsSize

假设K=3, 我们将原数组的后三个数字要放到新数组的前面，然后旧数组剩下的数字我们直接搬到新数组内

申请新数组等大的空间，先将后k个数据放到新数组中，再将剩下的数据挪到新数组中

最后我们还要将新数组的值挪到原数组中，为为原数组中的每个数进行重新赋值

那么这个代码的时间复杂度是多少呢？

在第一个循环中，时间复杂度是O(N),在第二个循环中时间复杂度是O(N)

那么总的时间复杂度就是O(2N)，根据规则，消掉系数，那么最后的时间复杂度就是O(N)

这种方法的时间复杂度就达到了O(N)

但是这种思路的空间复杂度也是O(N)

我们申请了新的空间，这个空间大小是N个，那么空间复杂度就是O(N)

这个思路虽然时间复杂度降到了O(N)，但是我们是拿空间复杂度换的

让时间复杂度为O(N),空间复杂度是O(1)

就是说明不需要额外申请空间

第一步将前n-k个数据逆置

第二步就是将后k个数据进行逆置

最后一步我们再将整体进行逆置

我们还要对逆置的次数进行取余，保证次数要小于数组的长度

我们对这个代码进行时间复杂度的分析

reverse函数 只有一个变量tmp，那么空间复杂度就是O(1)

对于逆置函数来说，我们调用了三次

第一次调用要交换的次数是(numsSize - k) / 2

第二次交换的次数是k / 2

第三次交换的次数是numsSize / 2

那么总的交换次数就是。

所以时间复杂度就是O(N)

对于rotate函数来说，我们调用了三次reverse函数，因为reverse函数的时间复杂度是O(N)，那么我们的rotate函数的时间复杂度就是O(N)

对于空间复杂度来说，rotaet本身仅仅只是调用了三次逆置函数，并没有额外开辟空间创建变量

所以空间复杂度是O(1)

如果对于逆置函数的时间复杂度还不理解的话你可以这么理解

时间复杂度的定义通常是最差的情况下

那么就是我们要进行整个数组的交换，这个就是最差的情况

假设数组有N个元素，那么我们就要交换N/2次，那么我们的时间复杂度就是O(N)

版权声明：

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！

转载请注明出处，原文链接：https://www.xkablog.com/rfx/48448.html