网站排名带照片怎么做,毕业设计在线交流平台,中国做外贸最好的网站,wordpress 在线教育 模板跌倒了#xff0c;就重新站起来#xff0c;继续向前走#xff1b;傻坐在地上是没用的。#x1f493;#x1f493;#x1f493; 目录
•✨说在前面
#x1f34b;知识点一#xff1a;算法的效率 • #x1f330;1.斐波那契数列的第n项 • #x1f330;2.算法的复杂度… 跌倒了就重新站起来继续向前走傻坐在地上是没用的。 目录
•✨说在前面
知识点一算法的效率 • 1.斐波那契数列的第n项 • 2.算法的复杂度
知识点二时间复杂度 • 1.时间复杂度的概念 • 2.大O的渐进表示法
复杂度的一般分析法则
总结求解复杂度的方法 • 3.时间复杂度的量级 • 4.时间复杂度增长趋势 • 5.时间复杂度计算案例
案例1单个同量级for循环
案例2多个同量级for循环
案例3常数控制的for循环
案例4strchr函数的时间复杂度
案例5冒泡排序的时间复杂度
案例6调整语句为ii*2的for循环
案例7二分查找的时间复杂度
案例8递归求阶乘
案例9递归求斐波那契数列的第n项
知识点三空间复杂度 • 1.空间复杂度的概念 • 2.空间复杂度计算案例
案例1冒泡排序的空间复杂度
案例2递归求阶乘
• ✨SumUp结语 •✨说在前面 亲爱的读者们大家好我们又见面了在之前的阶段我们学习了顺序表、链表包括单链表和双向链表还刷了一些算法OJ练习。这些练习我们有时可以有多种思路和方法解决那我们如何对这些方法进行取舍呢哪些方法是最优的呢为此我们必须进入学习时间复杂度和空间复杂度的相关知识相信你学习完后就可以回答这个问题了。 知识连线时刻直接点击即可 复习回顾 【数据结构】顺序表专题详解带图解析 【数据结构】单链表专题详细分析 【数据结构】双向循环链表专题解析 博主主页传送门愿天垂怜的博客 知识点一算法的效率 • 1.斐波那契数列的第n项
在讲解时间复杂度与空间复杂度之前我们先看一个简单的例子
练习写一个程序求出斐波那契数列的第n项的值。
方法1迭代法
long long Fibonacci(int n)
{int x1 1;int x2 1;int x3 1;while (n 3){x3 x1 x2;x1 x2;x2 x3;n--;}return x3;
}
方法2递归法
long long Fibonacci(int n)
{if (n 1 || n 2)return 1;return Fibonacci(n - 1) Fibonacci(n - 2);
}
由观察不难发现递归的写法明显要比迭代的写法要短的多那是不是就说明递归的写法就比迭代的写法更好呢其实不然实际上用递归来写的话它的运行效率将会大大降低。 比如求第50项就要先得到49项和48项要得到第49项就要得到48项和47项……它会执行很多很多次这是它效率不高的原因。
所以项数较大时我们还是用循环迭代的方式来实现。
所以说我们不能只根据程序的长短就果断地判断程序的好坏。 • 2.算法的复杂度
那究竟如何衡量算法的好坏呢就是要看程序的时间复杂度和空间复杂度。
算法在编写成可执行的程序后运行时需要耗费时间资源和空间内存资源因此衡量一个算法好坏一般从时间和空间两个维度来衡量的即时间复杂度和空间复杂度。
时间复杂度主要衡量一个算法的运行快慢而空间复杂度主要衡量一个算法运行所需要的额外空间。在计算机发展的早期计算机的存储容量很小所以对于空间复杂度很是在乎但结果计算机行业的迅速发展计算机的存储容量已经达到了很高的程度所以我们如今已经不需要再特别关注一个算法的空间复杂度转而更加关注他的时间复杂度。 知识点二时间复杂度 • 1.时间复杂度的概念
定义在计算机科学中算法的时间复杂度是一个函数它定量描述了该算法的运行时间。
一个算法执行所消耗的时间从理论上来说是不能算出来的只有你把你的程序放在机器上跑起来才能知道。但是我们需要每个算法都上机测试吗这显然非常麻烦所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比算法中的基本操作的执行次数为算法的时间复杂度。
即找到某条基本语句与问题规模N之间的数学表达式就是算出了该算法的时间复杂度。 • 2.大O的渐进表示法
实际问题中我们不需要精确的计算执行次数而只需要大概的执行次数即使用大O的渐进表示法。
公式如下 参数
• T(n)代码执行所需要的时间它是n的函数T(n)代表了算法的时间复杂度。
• n数据规模的大小但有可能不止一个如两个for循环分别循环m、n次则该参数为m、n。
• f(n)每行代码执行的次数总和它是n的函数但我们只关注最大量级的那一项。
• O表示T(n)与f(n)之间的关系为正比例即一个算法所花费的时间与其中语句的执行次数成正比。
复杂度的一般分析法则
1单端代码看高频比如for、while循环。
2多段代码取最大比如一段代码中有单循环和多重循环那么取多重循环的复杂度。
3嵌套代码求乘积例如递归、多重循环的结构。
4多个规模求加法比如算法中有两个参数控制了两个for循环那么此时复杂度取二者复杂度之和。
举例
//请计算一下Func1中count语句总共执行了多少次
void Func(int n)
{int count 0;for (int i 0; i n; i){for (int j 0; j n; j){count;}}for (int k 0; k 2 * n; k){count;}int M 10;while (M--){count;}printf(%d\n, count);
}
根据复杂度的分析原则在上面的这个函数Func1中第一个循环是嵌套结构for循环嵌套结构执行了n^2次第二个for循环执行了2n次最后一个while循环执行了10次。
由此这个函数中基本语句的执行次数f(n)的表达式为f(n)n^22n10所以T(n)O(n^22n10)。但是大O的渐进表示法并不具体代表代码真正的执行时间而是代表代码执行时间随数据规模n增长的变化趋势。
当n很大时比如1000、100000此时公式中的低阶、常量、系数三部分不左右增长趋势所以都可以忽略只关注最高阶的那一项就可以了。
所以最终Func的时间复杂度表示为T(n)O(n^2)。 总结求解复杂度的方法 1只关注循环执行次数最多的一段代码总复杂度等于量级最大的那段代码的复杂度 2加法法则若控制两个for循环的数量级相同则总复杂度取二者复杂度之和。 3乘法法则嵌套循环的复杂度等于嵌套内外代码复杂度的乘积。 • 3.时间复杂度的量级 多项式阶随着数据规模的增长算法的执行时间和空间占用按照多项式的比例增长包括O(1)常数阶、O(logn)对数阶、O(n)线性阶、O(nlogn)线性对数阶、O(n^2)平方阶、O(n^3)立方阶。
非多项式阶随着数据规模的增长算法的执行时间和空间占用暴增这类算法性能极差。包括 O(2^n)指数阶、O(n!)阶乘阶。 • 4.时间复杂度增长趋势
常见不同数量级的复杂度增长趋势图如下 另外有些算法的时间复杂度存在最好、平均和最快的情况
最坏情况代码在最坏情况下执行的时间复杂度即任意输入规模的最大运行次数上界。
平均情况代码在所有情况下执行的次数的加权平均值即任意输入规模的期望运行次数。
最好情况代码在最理想情况下执行的时间复杂度任意输入规模的最小运行次数下界。
比如在一个长度为N的数组中搜索数据x
最坏情况N次找到
平均情况N/2次找到
最好情况1次找到
在实际中一般情况关注的是算法的最坏运行情况所以数组中搜索数据的时间复杂度为O(N)。 • 5.时间复杂度计算案例
案例1单个同量级for循环
计算Func2的时间复杂度。
void Func2(int N)
{int count 0;for (int k 0; k 2 * N; k){count;}int M 10;while (M--){count;}printf(%d\n, count);
}
函数Func2中第一个for循环执行了2N次第二个while循环的执行次数是M但是M为已知量10量级最大的为2N所以Func2的时间复杂度为O(N)。 案例2多个同量级for循环
计算Func3的时间复杂度。
void Func3(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);
}
函数Func3中第一个for循环执行了M次第二个for循环执行了N次且M、N量级相同所以Func3的时间复杂度为O(MN)或O(max(MN))。
注意若MN则时间复杂度为O(M)若MN则时间复杂度为O(N)。 案例3常数控制的for循环
计算Func4的时间复杂度。
void Func4(int N)
{int count 0;for (int k 0; k 100; k){count;}printf(%d\n, count);
}
函数Func4中控制for循环的次数为常数代码不随n的增长而增长常数阶的时间复杂度为O(1)即Func4的时间复杂度为O(1)。 案例4strchr函数的时间复杂度
strchrstrchr() 用于查找字符串中的一个字符并返回该字符在字符串中第一次出现的位置。
strchr函数模拟实现代码如下
const char* my_strchr(const char* str, int character)
{assert(str);while (*str){if (*str character)return str;elsestr;}
}
在strchr查找的过程中最好的情况是字符character就在下一个字符一次就可以找到也就是常数阶此时时间复杂度为O(1)最坏的情况是字符character在离位置的无穷远处也就是线性阶。此时时间复杂度为O(N)取最坏的情况所以strchr的时间复杂度为O(N)。 案例5冒泡排序的时间复杂度
计算冒泡排序BubSort的时间复杂度。
void bubSort(int arr[], int length)
{assert(arr);int flag 1;while (flag length--){flag 0;for (int i 0; i length; i){if (arr[i] arr[i 1]){int temp arr[i];arr[i] arr[i 1];arr[i 1] temp;flag 1;}}}
}
冒泡排序中由类似案例2的嵌套循环结构但是像案例2这样的嵌套循环它的内层for循环的控制参数是不变的也就是说内部循环一共执行了M次每次执行内部循环都需要循环N次所以总共的执行次数是M*N这很好理解但现在冒泡排序的内部循环一共执行了length次而第一次for循环length次第二次length-1次第三次length-2次...若考虑最坏的情况最后到1次。这种情况怎么处理呢
显然内部for循环的循环次数是一个等差数列其中公差d2首项a11尾项anlength简写为n项数为length。对于这样一个等差数列我们可以对其求和所得到的结果不就是所有的执行次数了吗 根据高斯求和公式很容易计算出等差数列的前n项和即基本操作的执行次数显然为平方阶量级为N^2所以冒泡排序Bubsort的时间复杂度为O(N^2)。
其实对于案例2这样每次都是循环固定次数的嵌套或者说任意的双层嵌套都可以转化为数列求和的问题如案例2显然就是一个公差d0首项为N尾项为N项数为M的等差数列 根据高斯求和公式也能够分析出基本操作的执行次数即时间复杂度为O(MN)。 案例6调整语句为ii*2的for循环
计算Func5的时间复杂度。
void Func5(int n)
{int x 0;for (int i 1; i n; i * 2){x;}
}
函数Func5中这个for循环的调整语句为i*2即i每次都是前一次的两倍。这种循环是有规律的这个我们后面再说。我们先直接分析这个函数假设基本语句x执行了N次那么有循环语句可得 所以我们得到执行次数N为对数阶所以时间复杂度为O(logN)。这里需要注意为了方便起见当底数为2时我们直接将底数2省略不写 案例7二分查找的时间复杂度
计算二分查找BinarySearch的时间复杂度。
int BinarySearch(int arr[], int length, int x)
{assert(arr);int left 0;int right length - 1;while (left right){int mid left right - ((left - right) 1);if (arr[mid] x)left mid 1;else if (arr[mid] x)right mid - 1;else if (mid x)return x;}return -1;
}
在二分查找函数BinarySearch中如果我们直接观察while循环的话其实是不太好看出来的因为left和right时不时都在改变此时我们不要死盯代码一定要理解它的实际意义也可以看图进行观察 最好的情况我们很容易想到就是要查找的x就在中间我们一下就找到了此时是时间复杂度为O(1)。那最坏的情况呢其实就是当要查找的x在数组的两端的时候比如x是第一个元素此时我们设mid到x的距离为n则mid会以每次靠近一半的速度逼近第一个元素x也就是每次都除以2直到这个值等于1就找到了第一个元素。我们设循环执行了N次mid第一次的位置为n则 同样地如果x是最后一个元素也是同样的道理。显然为对数阶所以二分查找BinarySearch的
的时间复杂度为O(logN)。 案例8递归求阶乘
计算Fact的时间复杂度。
long long Fact(size_t N)
{if (0 N)return 1;return Fac(N - 1) * N;
}
这是一个递归求阶乘的函数。在函数Fact中我们假设N5的情况如下 可以发现每次递归的单个函数都是常数阶即O(1)而递归总共调用了516次Fact(5)、Fact(4)、Fact(3)、Fact(2)、Fact(1)、Fact(0)。
所以递归的函数我们先看单个函数内部的阶再看递归了多少次。如果是N那么每个函数为O(1)递归了N1次那么总共为(N1)O(1)所以递归求阶乘函数的时间复杂度为O(N)。 案例9递归求斐波那契数列的第n项
计算Fibonacci函数的时间复杂度。
long long Fibonacci(int n)
{if (n 1 || n 2)return 1;return Fibonacci(n - 1) Fibonacci(n - 2);
}
同样的道理我们看单个函数内部的阶显然为O(1)那递归了多少次呢 我们以n5为例此时我们能画出面类似于树状图的结构在数的每个节点都进而伸出两个节点第一行为个数为12^0第二行个数为22^1第三行个数为42^2...以此类推第n行的个数为2^n。但其实上大家能看到这颗树是歪的它的底部缺失了一块三角形的部分但是当n很大时这些缺失的部分相对于整体的个数其实就很少了由此我们可以将每一行的递归次数看做一项那整体就可以看做首项a11公比q2的等比数列求和得到的即是全体递归的总次数。 虽然真正的递归次数没有这么多但是它的量级是不会被影响的依然是指数阶所以用递归求斐波那契数列的第n项它的时间复杂度为O(2^N)。
稍许有些不严谨在二叉树的部分我们还会提到。 知识点三空间复杂度 • 1.空间复杂度的概念
空间复杂度也是一个数学表达式是对一个算法在运行过程中临时占用存储空间大小的亮度。 空间复杂度不是程序占用了多少bytes的空间因为这个也没太大意义所以空间复杂度算的是变量的个数。
空间复杂度计算规则基本和时间复杂度类似也是大O渐进表示法。
注意函数运行时所需要的栈空间存储参数、局部变量、一些寄存器信息等在编译期间已经确定好了因此空间复杂度主要通过函数在运行时候显式的额外空间来确定。 • 2.空间复杂度计算案例
案例1冒泡排序的空间复杂度
计算冒泡排序BubSort的空间复杂度。
void bubSort(int arr[], int length)
{assert(arr);int flag 1;while (flag length--){flag 0;for (int i 0; i length; i){if (arr[i] arr[i 1]){int temp arr[i];arr[i] arr[i 1];arr[i 1] temp;flag 1;}}}
}
在冒泡排序BubSort中创建了int flag 1int i 0两个变量为常数个所以冒泡排序的空间复杂度为O(1)。
注意空间复杂度算的是算法中额外开辟的空间所以数组arr和长度length并不算在内。 案例2递归求阶乘
计算Fact函数的空间复杂度。
long long Fact(size_t N)
{if (0 N)return 1;return Fac(N - 1) * N;
}
对于这样的一个递归函数每次递归都会在栈上创建栈帧空间函数栈帧每个栈帧使用了常数个空间所以空间复杂度为O(N)。 • ✨SumUp结语 数据结构的学习一定要多画图多理解多思考切忌直接抄写代码就认为自己已经会了一定到自己动手才能明白自己哪个地方有问题。 如果大家觉得有帮助麻烦大家点点赞如果有错误的地方也欢迎大家指出~
