北师大 网页制作与网站建设学做网站书籍

当前位置： 首页 > news >正文

北师大 网页制作与网站建设,学做网站书籍,wordpress 4.9.6 主题,个人网站能备案吗#x1f451;专栏内容#xff1a;数据结构⛪个人主页#xff1a;子夜的星的主页#x1f495;座右铭#xff1a;日拱一卒#xff0c;功不唐捐 文章目录一、前言二、时间复杂度1、定义2、大O的渐进表示法3、常见的时间复杂度三、空间复杂度1、定义2、常见的空间复杂度一、前… 专栏内容数据结构⛪个人主页子夜的星的主页座右铭日拱一卒功不唐捐 文章目录一、前言二、时间复杂度1、定义2、大O的渐进表示法3、常见的时间复杂度三、空间复杂度1、定义2、常见的空间复杂度一、前言 一个程序能用很多不同的算法来实现那么到底那种算法是效率最高的呢 对此我们有两种方法 第一种是事后统计法既在编写之后通过计时比较不同算法编写的程序的运行时间以此确定算法效率的高低。但是该方法的缺陷很大会受到测试环境、数据规模的影响。 第二种是事前分析法即在编写之前依据一些统计方法对算法进行粗略估算大致的估算出该算法的时间复杂度和空间复杂度通过对比复杂度来评判那种算法的效率更高。 可以说学会了如何分析一个算法的复杂度就拥有了未卜先知的能力即在这个算法被写出来之前就能大致评判出这个算法的好坏。 二、时间复杂度 1、定义 维基百科在计算机科学中算法的时间复杂度time complexity是一个函数它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述不包括这个函数的低阶项和首项系数。使用这种方式时时间复杂度可被称为是渐近的亦即考察输入值大小趋近无穷时的情况。 额…具体来举个例子吧。 void Func1(int N) { int count 0; // n*n次 for (int i 0; i N ; i) {for (int j 0; j N ; j){count;} } // 2*n次 for (int k 0; k 2 * N ; k) {count; } // 10次 int M 10; while (M–) {count; } printf(%d\n, count); }这个函数一共执行的基本操作次数为F(n)n22∗n10F(n)n^22*n10F(n)n22∗n10 但是我们计算复杂度的时候不一定需要计算这么精确的执行次数我们只需要计算出大概的执行次数就行了所以这里我们应该使用大O的渐进表示法。那么什么是大O表示法呢 2、大O的渐进表示法 大O符号Big O notation是用于描述函数渐进行为趋向于特定值或无穷大的数学符号。 上面函数一共执行的操作次数为F(n)n22∗n10F(n)n^22*n10F(n)n22∗n10 学过极限的都知道当nnn趋向于无穷的时候n22∗n10n^22*n10n22∗n10 中的2∗n2*n2∗n和10可以忽略不记。 所以用大O的渐进表示法上面函数的时间复杂度应该为O(n2)O(n^2)O(n2) 这里我们可以简单的总结一下方法 1、用常数1取代运行时间中的所有加法常数。 2、在修改后的运行次数函数中只保留最高阶项。 3、嵌套代码的复杂度等于嵌套内外代码复杂度的乘积。 4、如果最高阶项存在且不是1则去除与这个项目相乘的常数。 3、常见的时间复杂度 O(1)O(1)O(1)型 一般情况下要算法的执行时间不随问题规模 n 的增加而增大那么就是O(1)O(1)O(1)的时间复杂度 void Func(int n) {int count 0;for (int k 0; k 100; k){count;}printf(%d\n, count); }以上代码看似存在循环但是仔细看当循环到第十次的时候这个循环就停止了。 所以上面的时间复杂度为 O(1)O(1)O(1) O(logn)O(logn)O(logn)型 类似于二分查找、幂运算都是O(logn)O(logn)O(logn)的时间复杂度 void Func(int n) {int i1;while (i n) {i i * 2;} }以上代码变量 i 从 1 开始每循环一次就乘以 2。当大于n时循环结束。所以假设一共循环了xxx次,那么我们就可以得到2xn2^xn2xn 即xlog2nxlog_2nxlog2​n 忽略掉底数2则该时间复杂度为O(logn)O(logn)O(logn) 为什么可以忽略掉底数 高中学过的换底公式logbnlogba∗loganlog_bnlog_ba*log_anlogb​nlogb​a∗loga​n 现在假设底数不是2是3我们可以把log3nlog_3nlog3​n写成log32∗log2nlog_32*log_2nlog3​2∗log2​n根据前面的规矩如果最高阶项存在且不是1则去除与这个项目相乘的常数。 而这里的log32log_32log3​2是个常数可以直接去除。所以兜兜转转最后的时间复杂度还是O(logn)O(logn)O(logn) O(nlogn)O(nlogn)O(nlogn)型 void Func(int n) {for (int i 1; i n; i){int j 1;while (j n){j j * 2;}} }根据上面可以知道这个循环里面的循环的复杂度是O(logn)O(logn)O(logn)而这个循环又要执行n次所以算下来它的时间复杂度是O(nlogn)O(nlogn)O(nlogn) O(n)O(n)O(n)型 void Func(int n) {for (int i 1; i n; i){printf(我一共执行了n次哦);} }O(n2)O(n^2)O(n2)型 循环套循环每个循环都是n次 void Func(int n) {for (int i 1; i n; i){for (int j 1; j n; j){printf(我一共执行了n*n次哦);}} }O(m∗n)O(m*n)O(m∗n)型 void Func(int n,int m) {for (int i 1; i n; i){for (int j 1; j m; j){printf(看的出来我有那些不一样吗);}} }确实还有其他很多不同的时间复杂度比如O(2n)、O(n!)O(2^n)、O(n!)O(2n)、O(n!)…但是这些时间复杂度都太高了以至于高到很多计算机都承受不了所以比较少见。 三、空间复杂度 1、定义 维基百科在计算机科学中一个算法或程序的空间复杂度定性地描述该算法或程序运行所需要的存储空间大小。空间复杂度是相应计算问题的输入值的长度的函数它表示一个算法完全执行所需要的存储空间大小。和时间复杂度类似空间复杂度通常也使用大O记号来渐进地表示例如O(n)、O(nlogn)O(n)、O(nlogn)O(n)、O(nlogn)其中n用来表示输入的长度该值可以影响算法的空间复杂度。 就像时间复杂度的计算不考虑算法所使用的空间大小一样空间复杂度也不考虑算法运行需要的时间长短。 注意函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。 2、常见的空间复杂度 O(1)型O(1)型O(1)型 无论 n 的值如何变化代码在执行过程中开辟的内存空间是固定的 void Func(int n) {int i 0; int sum 0;for (i 1; i n; i){sum sum i;} }这段代码之开辟了sum和i两个int类型的空间大小是固定的。 所以这段代码的空间复杂度为O(1)O(1)O(1) O(n)型O(n)型O(n)型 随着n的值的增大开辟的空间也逐渐增大 long long Fac(size_t N) {if(N 0)return 1;return Fac(N-1)*N; }这段代码递归调用了N次开辟了N个栈帧每个栈帧使用了常数个空间。 所以这段代码的空间复杂度为O(N)O(N)O(N) O(n2)型O(n^2)型O(n2)型 int** fun(int n) {int ** s (int **)malloc(n * sizeof(int *));while(n–)snmalloc(n * sizeof(int));return s;}此处开辟的是一个二维数组数组有n行每行分别有1,2,3,…n列所以是n(n1)/2n(n 1)/2n(n1)/2个元素空间空间复杂度为n2n^2n2