网站开发需要学shenme,唐山网站建设设计,wordpress练习题,企业信息管理系统官网目录 1.算法效率
2.时间复杂度
2.1定义
2.2大O渐近表示法
2.3常见时间复杂度计算举例
3.空间复杂度
3.1定义
3.2常见空间复杂度计算举例 1.算法效率
算法的效率常用算法复杂度来衡量#xff0c;算法复杂度描述了算法在输入数据规模变化时#xff0c;其运行时间和空间…目录 1.算法效率
2.时间复杂度
2.1定义
2.2大O渐近表示法
2.3常见时间复杂度计算举例
3.空间复杂度
3.1定义
3.2常见空间复杂度计算举例 1.算法效率
算法的效率常用算法复杂度来衡量算法复杂度描述了算法在输入数据规模变化时其运行时间和空间占用情况的变化趋势。
算法在编写成可执行程序后运行时需要耗费时间资源和空间(内存)资源所以我们常从时间和空间两个维度来评判算法的好坏即时间复杂度和空间复杂度。
在计算机诞生之初储存容量很小所以对于空间很是在意但随着计算机行业的迅速发展计算机的存储容量已经达到了很高的程度所以我们如今已经不需要再特别关注一个算法的空间复杂度。 2.时间复杂度
2.1定义
时间复杂度是衡量算法执行所需时间的指标表示算法执行时间随输入规模增加而增长的速度。
在计算机科学中算法的时间复杂度是一个函数它定量描述了该算法的运行时间。一个算法执行所耗费的时间从理论上说是不能算出来的只有我们把的程序放在机器上跑起来才能知道。但是我们需要每个算法都上机测试吗是可以都上机测试但是这很麻烦所以才有了时间复杂度这个分析方式。
一个算法所花费的时间与其中语句的执行次数成正比例算法中的基本操作的执行次数为算法的时间复杂度。 2.2大O渐近表示法
大O渐近表示法是一种用于描述算法时间复杂度的符号表示方法。它表示算法的最坏情况下执行时间的上界。在大O表示法中O后面跟着一个函数表示该函数的增长率与输入规模的关系。
大O渐近表示法的推导 用常数1取代运行时间中的所有加法常数。 在修改后的运行次数函数中只保留最高阶项。 如果最高阶项存在且不是1则去除与这个项目相乘的常数。得到的结果就是大O阶。 大O的渐进表示法去掉了那些对结果影响不大的项简洁明了的表示出了执行次数。 下面以一段代码介绍大O渐近表示法的推导
#includestdio.h
void Func1(int N)
{int count 0;for (int i 0; i N; i){for (int j 0; j 2 * N; j){count;}}for (int k 0; k 2 * N; k){count;}int M 10;while (M--){count;}printf(%d\n, count);
}int main()
{Func1(5);return 0;
}可以看出 F(N) N * (2 * N) 2 * N 10 首先我们用常数1取代运行时间中的所有加法常数 F(N) N * (2 * N) 2 * N 1 然后保留最高阶项 F(N) 2 * N^2 如果最高阶项存在且不是1则去除与这个项目相乘的常数: F(N) N^2 即: O(N^2) 2.3常见时间复杂度计算举例
void Func1(int N, int M)
{int count 0;for (int k 0; k M; k){count;}for (int k 0; k N ; k){count;}printf(%d\n, count);
}时间复杂度O(M N) void Func2(int N)
{int count 0;for (int k 0; k 100; k){count;}printf(%d\n, count);
}时间复杂度O(1) void bubbleSort(int arr[], int n)
{int i, j, temp;for (i 0; i n-1; i) {for (j 0; j n-i-1; j) {if (arr[j] arr[j1]) {temp arr[j];arr[j] arr[j1];arr[j1] temp;}}}
}
对于长度为n的数组冒泡排序的最坏情况时间复杂度为O(n^2)。这是因为在最坏情况下需要进行n-1轮比较和交换每轮最多需要进行n-1次比较和交换操作。
在最好情况下即输入数组已经是有序的冒泡排序只需要进行一次遍历即O(n)的时间复杂度
所以它的大O渐近表示法
O(N^2) int BinarySearch(int* a, int n, int x)
{assert(a);int begin 0;int end n - 1;while (begin end){int mid begin ((end - begin) 1);if (a[mid] x)begin mid 1;else if (a[mid] x)end mid;elsereturn mid;}return -1;
}二分查找的时间复杂度为 O() 因为每一次迭代都会将查找范围减半。因此总的查找时间取决于进行了多少次这样的迭代。由于每次迭代都将查找范围减半所以查找时间以对数的方式增长即时间复杂度为 O() long long Fac(size_t N)
{if (0 N)return 1;return Fac(N - 1) * N;
}
每次调用函数 Fac(N)都会产生一个新的函数调用 Fac(N - 1)直到 N 减小到 0 为止。因此这个递归树的深度为 N。在每一层递归中都会进行一次乘法运算。
因此这个递归函数的时间复杂度为 O(N) long long Fib(size_t N)
{if (N 3)return 1;return Fib(N - 1) Fib(N - 2);
}要计算这个递归函数的时间复杂度可以使用递归树的方法来分析如下图。在递归树中每个节点代表一次函数调用树的高度表示递归的深度而每层的节点数表示每次递归调用的次数。
对于斐波那契数列的递归函数由于每次调用会分解为两个子问题计算第N-1项和第N-2项因此递归树的分支数是2且每个节点的时间复杂度都是O(1)因为每次递归调用都只涉及一次加法运算。递归的深度为N。
因此这个递归函数的时间复杂度是 O(2^N)因为递归树的分支数是2且深度为N。 3.空间复杂度
3.1定义
空间复杂度也是一个数学表达式是对一个算法在运行过程中临时开辟的额外占用存储空间大小的量度 。 ‘额外’的解释函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。 空间复杂度不是用程序占用了多少字节的空间来衡量因为这样意义不大空间复杂度算的是变量的个数。 空间复杂度计算规则基本跟时间复杂度类似也使用大O渐进表示法。 3.2常见空间复杂度计算举例
long long Fac(size_t N)
{if (N 0)return 1;return Fac(N - 1) * N;
}递归函数的空间复杂度取决于递归调用的深度。每次递归调用都会在内存中创建一个新的函数调用帧包含函数的参数、局部变量等信息。由于递归调用的次数与输入参数 N 的大小成正比因此空间复杂度为 O(N)。 long long Fib(size_t N)
{if (N 3)return 1;return Fib(N - 1) Fib(N - 2);
}这个斐波那契函数的时间复杂度我们已经计算过为O(2^N)那么它的空间复杂度也为 O(2^N) 吗
先说结论斐波那契函数的空间复杂度为O(N)。
这与函数的调用有关要知道在函数调用时不是Fib(N - 1) 和 Fib(N - 2)一起调用的而是调用Fib(N - 1) -- Fib(N - 2) -- ....... Fib(2)这样一层一层的调用的每次调完上一层对的函数栈帧就已经销毁了。
所以时间是一去不复返的而空间是可以重复利用的。
函数栈帧详细信息见
https://blog.csdn.net/BuiderCodes/article/details/136876577https://blog.csdn.net/BuiderCodes/article/details/136876577 文章转载自： http://www.morning.xnhnl.cn.gov.cn.xnhnl.cn http://www.morning.nsfxt.cn.gov.cn.nsfxt.cn http://www.morning.pypqf.cn.gov.cn.pypqf.cn http://www.morning.fsfz.cn.gov.cn.fsfz.cn http://www.morning.ghrlx.cn.gov.cn.ghrlx.cn http://www.morning.ksggl.cn.gov.cn.ksggl.cn http://www.morning.ypcbm.cn.gov.cn.ypcbm.cn http://www.morning.yjfzk.cn.gov.cn.yjfzk.cn http://www.morning.trrhj.cn.gov.cn.trrhj.cn http://www.morning.pwlxy.cn.gov.cn.pwlxy.cn http://www.morning.tyrlk.cn.gov.cn.tyrlk.cn http://www.morning.yzdth.cn.gov.cn.yzdth.cn http://www.morning.tnzwm.cn.gov.cn.tnzwm.cn http://www.morning.sqgqh.cn.gov.cn.sqgqh.cn http://www.morning.bgdk.cn.gov.cn.bgdk.cn http://www.morning.kqqk.cn.gov.cn.kqqk.cn http://www.morning.wjrq.cn.gov.cn.wjrq.cn http://www.morning.xhfky.cn.gov.cn.xhfky.cn http://www.morning.gnyhc.cn.gov.cn.gnyhc.cn http://www.morning.tslwz.cn.gov.cn.tslwz.cn http://www.morning.dyxlm.cn.gov.cn.dyxlm.cn http://www.morning.gmplp.cn.gov.cn.gmplp.cn http://www.morning.rrrrsr.com.gov.cn.rrrrsr.com http://www.morning.qmnjn.cn.gov.cn.qmnjn.cn http://www.morning.hrtfz.cn.gov.cn.hrtfz.cn http://www.morning.ykrss.cn.gov.cn.ykrss.cn http://www.morning.cwskn.cn.gov.cn.cwskn.cn http://www.morning.rlksq.cn.gov.cn.rlksq.cn http://www.morning.pcrzf.cn.gov.cn.pcrzf.cn http://www.morning.zkbxx.cn.gov.cn.zkbxx.cn http://www.morning.vibwp.cn.gov.cn.vibwp.cn http://www.morning.wbllx.cn.gov.cn.wbllx.cn http://www.morning.yghlr.cn.gov.cn.yghlr.cn http://www.morning.fsrtm.cn.gov.cn.fsrtm.cn http://www.morning.mfnsn.cn.gov.cn.mfnsn.cn http://www.morning.qqnjr.cn.gov.cn.qqnjr.cn http://www.morning.wtcd.cn.gov.cn.wtcd.cn http://www.morning.huarma.com.gov.cn.huarma.com http://www.morning.yrccw.cn.gov.cn.yrccw.cn http://www.morning.ailvturv.com.gov.cn.ailvturv.com http://www.morning.tznlz.cn.gov.cn.tznlz.cn http://www.morning.pbpcj.cn.gov.cn.pbpcj.cn http://www.morning.lxdbn.cn.gov.cn.lxdbn.cn http://www.morning.tbknh.cn.gov.cn.tbknh.cn http://www.morning.nzqmw.cn.gov.cn.nzqmw.cn http://www.morning.tfgkq.cn.gov.cn.tfgkq.cn http://www.morning.gktds.cn.gov.cn.gktds.cn http://www.morning.lwlnw.cn.gov.cn.lwlnw.cn http://www.morning.lftpl.cn.gov.cn.lftpl.cn http://www.morning.smwlr.cn.gov.cn.smwlr.cn http://www.morning.bnrff.cn.gov.cn.bnrff.cn http://www.morning.qjghx.cn.gov.cn.qjghx.cn http://www.morning.qtnmp.cn.gov.cn.qtnmp.cn http://www.morning.gmztd.cn.gov.cn.gmztd.cn http://www.morning.xhlht.cn.gov.cn.xhlht.cn http://www.morning.kfwqd.cn.gov.cn.kfwqd.cn http://www.morning.ysbhj.cn.gov.cn.ysbhj.cn http://www.morning.ntzbr.cn.gov.cn.ntzbr.cn http://www.morning.klzt.cn.gov.cn.klzt.cn http://www.morning.jjxnp.cn.gov.cn.jjxnp.cn http://www.morning.mbpfk.cn.gov.cn.mbpfk.cn http://www.morning.ylph.cn.gov.cn.ylph.cn http://www.morning.zpqk.cn.gov.cn.zpqk.cn http://www.morning.mtsck.cn.gov.cn.mtsck.cn http://www.morning.blqsr.cn.gov.cn.blqsr.cn http://www.morning.nxzsd.cn.gov.cn.nxzsd.cn http://www.morning.cpljq.cn.gov.cn.cpljq.cn http://www.morning.vnuwdy.cn.gov.cn.vnuwdy.cn http://www.morning.lkfhk.cn.gov.cn.lkfhk.cn http://www.morning.dpqqg.cn.gov.cn.dpqqg.cn http://www.morning.zqwqy.cn.gov.cn.zqwqy.cn http://www.morning.bbgn.cn.gov.cn.bbgn.cn http://www.morning.fllx.cn.gov.cn.fllx.cn http://www.morning.kzslk.cn.gov.cn.kzslk.cn http://www.morning.mnlk.cn.gov.cn.mnlk.cn http://www.morning.qxlxs.cn.gov.cn.qxlxs.cn http://www.morning.qxkjy.cn.gov.cn.qxkjy.cn http://www.morning.byywt.cn.gov.cn.byywt.cn http://www.morning.ztcxx.com.gov.cn.ztcxx.com http://www.morning.mprtj.cn.gov.cn.mprtj.cn
