淘宝 网站建设,网站如何做支付接口,vps主机上搭建网站,wordpress 卡密插件算法时间空间复杂度计算—空间复杂度 空间复杂度定义影响空间复杂度的因素算法在运行过程中临时占用的存储空间讲解 计算方法例子1、空间算法的常数阶2、空间算法的线性阶#xff08;递归算法#xff09;3、二分查找分析方法一#xff08;迭代法#xff09;方法二#xff… 算法时间空间复杂度计算—空间复杂度 空间复杂度定义影响空间复杂度的因素算法在运行过程中临时占用的存储空间讲解 计算方法例子1、空间算法的常数阶2、空间算法的线性阶递归算法3、二分查找分析方法一迭代法方法二递归法 4、斐波那契数列方法一迭代法方法二递归法 空间复杂度定义
空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。 一个算法在计算机存储器上所占用的存储空间包括程序代码所占用的空间输入数据所占用的空间和辅助变量所占用的空间这三个方面。
影响空间复杂度的因素 注意 一个算法的空间复杂度只考虑在运行过程中为局部变量分配的存储空间的大小它包括为参数表中形参变 量分配的存储空间和为在函数体中定义的局部变量分配的存储空间两个部分。若一个算法为递归算法其空间复杂度为递归所使用的堆栈空间的大小。它等于一次调用所分配的临时存储空间的大小乘以被调用的次数(即为递归调用的次数加1这个1表示开始进行的一次非递归调用) 递归的空间复杂度 每次递归所开空间*深度。
算法在运行过程中临时占用的存储空间讲解
1、有的算法只需要占用少量的临时工作单元而且不随问题规模的大小而改变我们称这种算法是“就地”进行的是节省存储的算法下面会介绍。
2、有的算法需要占用的临时工作单元数与解决问题的规模n有关它随着n的增大而增大当n较大时将占用较多的存储单元例如快速排序和归并排序算法就属于这种情况。
计算方法
①忽略常数用O(1)表示 ②递归算法的空间复杂度递归深度n*每次递归所要的辅助空间 ③对于单线程来说递归有运行时堆栈求的是递归最深的那一次压栈所耗费的空间的个数因为递归最深的那一次所耗费的空间足以容纳它所有递归过程。
例子
1、空间算法的常数阶 如上图这里有三个局部变量分配了存储空间所以f(n) 1 1 1 3根据上面的法则该函数不受n的影响且为常数项所以空间复杂度记作O(1)。这种与问题的大小无关n的多少执行时间恒定的算法我们称之为具有O(1)的空间复杂度又叫常数阶。
2、空间算法的线性阶递归算法 如上图这是一个递归算法计算从n (n-1) (n-2) … 2 1的和 每当执行一次该函数就会为tmp分配一个临时存储空间所以f(n) 1*(n-11) n函数是受n影响的所以空间复杂度记为O(n)。
3、二分查找分析 方法一迭代法 /// summary/// 二分查找/// /summary/// param namearr查找数组/param/// param namelen数组长度/param/// param namenum查找项/param/// returns/returnsint BinarySearch(int[] arr,int len,int num){int left 0;int right len - 1;int mid;while (left right){mid (left right) / 2;if (arr[mid] num)right mid - 1;else if (arr[mid] num)left mid 1;elsereturn mid;}return -1;}时间复杂度 left、right、mid运算次数 f(n1) 1 1 1 3 我们将While循环中的运算作为一个整体看待每次都是折半运算次数 f(n2) log2^n 总运行次数 f(all) f(n1)f(n2) 3 log2 ^ n 时间复杂度记为:O(log2^n) 空间复杂度 算法中left、right、mid只创建的次数 s(n) 1 1 1 3 空间复杂度记为:O(1)
方法二递归法 /// summary/// 二分查找(递归法)/// /summary/// param namearr/param/// param nameleft/param/// param nameright/param/// param namenum/param/// returns/returnsint BinarySearchRecursion(int[] arr,int left,int right,int num){int mid (left right) / 2;if (left right){if (arr[mid] num) {right mid - 1;return BinarySearchRecursion(arr,left,right,num);}else if (arr[mid] num){left mid 1;return BinarySearchRecursion(arr,left,right,num);}elsereturn mid;}else{return -1;}}时间复杂度 运行次数 f(n) log2 ^ n 时间复杂度记为:O(log2^n) 空间复杂度 因为整个算法中mid只创建的次数 s(n) log2 ^ n 空间复杂度记为:O(log2 ^ n) 4、斐波那契数列
斐波那契数列Fibonacci sequence又称黄金分割数列、因数学家列昂纳多·斐波那契Leonardoda Fibonacci以兔子繁殖为例子而引入故又称为“兔子数列”指的是这样一个数列1、1、2、3、5、8、13、21、34、…… 这个数列从第3项开始每一项都等于前两项之和。
如果设F(n为该数列的第n项n∈N*那么这句话可以写成如下形式:F(n)F(n-1)F(n-2)
显然这是一个线性的递推数列。 通项公式 上面就是斐波那契数列的递推公式这样一个完全是自然数的数列通项公式却是用无理数来表达的。而且当n趋向于无穷大时前一项与后一项的比值越来越逼近黄金分割0.618 递推是公式是求解斐波那契数列的一个方法我们当然也可以用计算机编写程序来求解。
方法一迭代法 /// summary/// 斐波那契迭代法/// /summary/// param namen/param/// returns/returnsint Fibonacci(int n){if (n 0)return -1;if (n 1 || n 2)return 1;else{int num 0;int a 1;int b 1;while (n - 2 0){num a b;a b;b num;n--;}return num;}}时间复杂度 while以外的算法语句都忽略不计(不随n的变化而变化) while算法语句所有语句 f(n) 4 *n - 2 4n - 8 时间复杂度记为:O(n) 空间复杂度 算法中num、a、b只创建1次 s(n) 1 1 1 3 空间复杂度记为:O(1) 方法二递归法
/// summary/// 斐波那契递归法/// /summary/// param namen/param/// returns/returnsint FibonacciRecursion(int n){if (n 0)return -1;if (n 1 || n 2)return 1;return FibonacciRecursion(n - 1) FibonacciRecursion(n - 2);}时间复杂度 递归调用的形参有两个n - 1 和 n - 2 时间复杂度记为:O(2^n) 空间复杂度 递归的空间复杂度 n 1* 调用的深度 空间复杂度记为:O(n)这里可以简单的根据二叉树的层来进行计算
