石家庄便宜网站制作,桂城网站制作公司,广州工商注册核名查询系统,管理软件erpYan英杰的博客 悟已往之不谏 知来者之可追 目录
空间复杂度
案例1:计算BubbleSort的空间复杂度#xff1f;
案例2:计算斐波那契额数列的前N项的空间复杂度
案例3:计算阶乘递归Fac的空间复杂度#xff1f;
案例4:F1和F2两函数是否使用的同一块空间
案例5:计算该… Yan英杰的博客 悟已往之不谏 知来者之可追 目录
空间复杂度
案例1:计算BubbleSort的空间复杂度
案例2:计算斐波那契额数列的前N项的空间复杂度
案例3:计算阶乘递归Fac的空间复杂度
案例4:F1和F2两函数是否使用的同一块空间
案例5:计算该程序的空间复杂度
案例6:经典OJ(难度中等) 空间复杂度 空间复杂度也是一个数学表达式是对一个算法在运行过程中临时占用存储空间大小的量度 。 空间复杂度计算规则基本跟实践复杂度类似也使用大O渐进表示法。 注意函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。 案例1:计算BubbleSort的空间复杂度 // 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;}
} 分析: 注空间复杂度本质是:计算因为程序导致额外开辟的空间个数 此时该程序额外开辟了三个变量end exchange i又因为空间复杂度同样使用的是大O表达式所以我们由此得出空间复杂度为O(N) 提问: 当时我在计算该程序的空间复杂度有个疑问为什么不把数组算进去 这是因为我们在计算之前就已经开辟了数组的栈帧空间开始前就给出了所以不用在空间复杂度内加上数组的大小 案例2:计算斐波那契额数列的前N项的空间复杂度 //计算斐波那契额数列的前N项的空间复杂度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 n; i){fibArray[i] fibArray[i - 1] fibArray[i - 2];}return fibArray;
} 分析: 我们当前的变量为0但是我们要求第N项的空间复杂度所以我们开辟了n1块空间用来计算前N项和的空间复杂度O(N1)为其空间复杂度但是大O的渐进表示法我们计算出斐波那契额数列前N项和的空间复杂度为O(N) 案例3:计算阶乘递归Fac的空间复杂度 //计算阶乘递归Fac的空间复杂度
long long Fac(size_t N)
{if (N 0)return 1;return Fac(N - 1) * N;
} 分析 由于该程序为递归导致因为程序我们需要不断的开辟新的栈帧空间(每次传参均需要开辟一块新的空间)维护所以此程序的空间复杂度为O(N) 提问: 为什么开辟栈帧空间后需要额外再开辟新的栈帧空间 主要是因为栈帧空间只有在函数结束后,才会销毁而递归时函数其实并未销毁这也导致了其不断开辟新的栈帧空间也因为该程序的空间复杂度为O(N) 图解: 案例4:F1和F2两函数是否使用的同一块空间 //F1和F2两函数是否使用的同一块空间
void F2()
{int b 0;printf(%p\n,b);
}
void F1()
{int a 0;printf(%p\n,a);
}int main()
{F1();F2();return 0;
} 解析: 当调用F1函数时在Main函数低地址处进行压栈当出了F1函数函数销毁同时它用过的栈帧空间返回到内存中当我们再调用F2时F2继续在Main函数低地址处压栈所以他俩所维护的栈帧空间其实是同一块 图解: 提问: 那如何修改才能使两个函数指向不同栈帧空间 分析: 当我们在F1中调用F2时使得F1函数无法释放栈帧空间F2就必须在F1低地址处压栈此时他们两个维护的栈帧空间则不相同 图解 案例5:计算该程序的空间复杂度 //计算该程序的空间复杂度
long long Fib(size_t N)
{if (N3){return 1;}return Fib(N-1) - Fib(N-2);
}解析 为了详解这道题我们要先清楚其时间复杂度如何计算 由此看出其时间复杂度为O(2^N) 当我们弄懂其时间复杂度后以该时间复杂度为原型上面为什么要弄懂函数维护的空间其实也是有原因的当Fib(2)销毁后调用Fib(1)我们可以由此看出其实Fib(2)和Fib(1)维护的是同一块栈帧空间,销毁后再返回到上一次再销毁再调用其他函数其实总共维护的栈帧空间为N块 图解: 注:时间一去不复返无法重复利用但是空间用了之后归还可以重复利用 案例6:经典OJ(难度中等) 示例 1: 输入: nums [1,2,3,4,5,6,7], k 3 输出: [5,6,7,1,2,3,4] 解释: 向右轮转 1 步: [7,1,2,3,4,5,6] 向右轮转 2 步: [6,7,1,2,3,4,5] 向右轮转 3 步: [5,6,7,1,2,3,4] 示例 2: 输入nums [-1,-100,3,99], k 2 输出[3,99,-1,-100] 解释: 向右轮转 1 步: [99,-1,-100,3] 向右轮转 2 步: [3,99,-1,-100] 解析: 我们可以对其进行翻转前k项进行翻转后N-k进行翻转最后进行整体翻转 图解 错误示范: void reverse(int* nums,int begin ,int end)
{while (begin end){int tmp nums[begin];nums[begin] nums[end];nums[end] tmp;begin;end--;}}
void rotate(int* nums, int numsSize, int k)
{reverse(nums,0,numsSize-k-1);reverse(nums,numsSize-k,numsSize-1);reverse(nums, 0, numsSize - 1);
} 错误原因: 当数组的输入的个数小于输入的数组大小就会出现数组越界访问的问题所以导致了报错 解决办法 void reverse(int* nums,int begin ,int end)
{while (begin end){int tmp nums[begin];nums[begin] nums[end];nums[end] tmp;begin;end--;}}
void rotate(int* nums, int numsSize, int k)
{if (k numsSize){k % numsSize;}reverse(nums,0,numsSize-k-1);reverse(nums,numsSize-k,numsSize-1);reverse(nums, 0, numsSize - 1);
}
