网站建设域名和空间续费,河南省住建局官网,肇东市网站,怎么建立博客网站上一篇文章学习了#xff1a;如何分析、统计算法的执行效率和资源消耗#xff1f; 点击链接查看上一篇文章#xff1a;复杂度分析上
今天的文章学习以下内容#xff1a;
最好情况时间复杂度最坏情况时间复杂度平均情况时间复杂度均摊时间复杂度
1、最好与最坏情况时间复…上一篇文章学习了如何分析、统计算法的执行效率和资源消耗 点击链接查看上一篇文章复杂度分析上
今天的文章学习以下内容
最好情况时间复杂度最坏情况时间复杂度平均情况时间复杂度均摊时间复杂度
1、最好与最坏情况时间复杂度
我们首先来看一段代码利用上一篇文章学习的知识看看能否分析出它的时间复杂度。
// n 表示数组 array 的长度
int find(int[] array, int n, int x) {int i 0;int pos -1;for (; i n; i) {if (array[i] x) {pos i;break;}}return pos;
}
这段代码很简单就是在一个数组中找到一个数X的下标将其返回。
利用上一篇文章学习的大O表示法来分析时间复杂度的话有一些问题。if循环中有一个breadk语句当条件成立得到下标值立马退出循环。那么时间复杂度就不能笼统的说是On。
因为当想要查找的数就在第一个位置时时间复杂度实际上是O1当想要查找的数在最后一个位置的时候时间复杂度是On。那么这个时候我们就需要引入几个新名词最好情况时间复杂度最坏情况时间复杂度。
很容易理解。
最好情况时间复杂度就是在最理想的情况下执行代码需要的时间复杂度。就像上述代码如果想要查找的数就是数组中的第一个位置那么时间复杂度就是O1此时就是最好情况时间复杂度。最坏情况时间复杂度是在最不理想的情况下执行代码需要的时间复杂度。还是如上述代码入股我们想要查找的数在数组的最后一个位置那么时间复杂度就是On此时就是最坏情况时间复杂度。
其实还有一种情况就是我们想要查找的数不在第一个位置也不在最后一个位置的时候。此时的时间复杂度是多少呢这种情况下叫做平均情况时间复杂度。
那么平均情况时间复杂度如何计算它是多少呢
2、平均情况时间复杂度
还是拿上面的代码做例子。
想要计算出它的平均情况时间复杂度有两种方法一种不严谨的感官上的方法一种严格的概率上的方法。
不严谨的感官上的方法
我们知道想要查找的数据x有两种情况的存在一种是存在数组的0~n-1的某一个位置n种可能一种是不在这个数组中1中可能就是不在数组中。这两种情况一共有n1种可能。对于在数组中的n中可能中每一种查找的次数分别是1,2,3,4…n。对于不在数组中的这种可能查找次数是n。所以可以这么计算平均情况时间复杂度
(123...nn)/(n1)n(n3)/2(n1)上一篇文章我们知道利用大O表示法可以将计算结果的系数低阶常量去掉。那么上述的结果就是On。
为什么说他不严谨呢考虑以下情况。要找的数x存在于数组中与不存在于数组中的概率是否一样x存在的话。它存在于数组中每个位置的概率是否一样
很明显上述方法没有考虑概率的问题。
概率的方法
现在假设x出现在数组中与不出现在数组中的概率是相等的都是1/2.同时假设x如果出现在数组中则它存在数组中的每一个位置的概率都是一样的1/n。那么可以用如下方法计算平均情况时间复杂度。
1×1n×122×1n×123×1n×12...n×1n×12n×123n141 \times \frac{1}{n} \times \frac{1}{2}2 \times \frac{1}{n} \times \frac{1}{2} 3 \times \frac{1}{n} \times \frac{1}{2} ...n \times \frac{1}{n} \times \frac{1}{2} n \times \frac{1}{2} \frac{3n1}{4}1×n1×212×n1×213×n1×21...n×n1×21n×2143n1
利用大O表示法来表示的话依然是On。这就是上面那段代码的平均情况时间复杂度。
一般情况下我们只是用其中一种复杂度来分析问题就够了不需要费力去求解三种时间复杂度。只有在时间复杂度有量级的差距时才会在不同的情况下使用不同的时间复杂度。
3、均摊时间复杂度
上面学会了最好最坏与平均时间复杂度。还有一种时间复杂度叫做均摊时间复杂度。 为了理解均摊时间复杂度我们先来看一个代码 // array 表示一个长度为 n 的数组// 代码中的 array.length 就等于 nint[] array new int[n];int count 0;void insert(int val) {if (count array.length) {int sum 0;for (int i 0; i array.length; i) {sum sum array[i];}array[0] sum;count 1;}array[count] val;count;}
上述代码的意思是往数组中插入数据。当数组没有满的时候直接在最后插入当数组满的时候先把数组的所有元素求和然后清空数组将求得的和放到数组的第一个位置然后将要插入的数插到第二个位置聪明的人已经发现它其实就是一个求输入流中所有数字的和至于清空数组这个只是将下标count从末尾挪到第二个位置就可以认为是清空数组。
利用上述的分析我们可以求得
最好情况时间复杂度O1因为数组不满的时候直接插入不用计算和。最坏情况时间复杂度On因为此时数组满了需要遍历一遍数组然后求和。
平均时间复杂度还可以利用上述的概率分析法来计算。假设数组长度是n往数组插入数据会有两种情况发生。数组没满时插入的时间复杂度是O1且插入的位置有n种可能。数组满时插入的时间复杂度是On插入的位置只有一种可能。所以一共有n1种可能插入的位置且插入到它们位置的概率是一样的都是1/n1。所以可以利用下面的方法计算平均情况时间复杂度 1×1n12×1n13×1n1...n×1n1n×1n1O11 \times \frac{1}{n1}2 \times \frac{1}{n1} 3 \times \frac{1}{n1} ...n \times \frac{1}{n1} n \times \frac{1}{n1} O11×n112×n113×n11...n×n11n×n11O1
所以
平均情况时间复杂度O1
上述计算平均时间复杂度的方法不管怎么样还是有一些复杂。毕竟我们不是研究数学的。所以还是希望尽可能简单。
针对上面的两个代码例子一个是find函数一个是insert函数。看看他们有什么不同。find函数是最极端的情况下时间复杂度是O1大多数的情况下时间复杂度是On而insert函数是大多数情况下的时间复杂度是O1只有极端的情况下时间复杂度是On。
而且对于insert函数它的O1出现的是连续出现多次然后出现一次On时间复杂度。这具有一种时序关系。
针对这种情况给出一种特殊的时间复杂度分析方法均摊时间复杂度。可以通过摊还分析法的带均摊时间复杂度。那么针对insert函数如何通过摊还分析法来得到均摊时间复杂度呢
首先对于insert函数大多是出现O1时间复杂度的一共出现n次O1时间复杂度后才出现一次On时间复杂度。虽然On时间复杂度消耗的时间比较多但是O1时间复杂度出现的次数多我们可以将On消耗的时间均摊给其他n个O1时间复杂度操作上的话对于O1时间复杂度也并不会有多大的影响就好比100个人共同抬100斤水泥而另外又有一个人在抬100斤水泥如果这个人把水泥平均分给那100人那100人也才每个人多抬了一斤的水泥这相比让那一个人抬100斤水泥简直不要太轻松。 所以对于insert函数均摊时间复杂度为O1。这等于大多数情况下的时间复杂度。
综上
均摊时间复杂度为O1
由以上的分析我们得出大概在以下情况下可以使用摊还分析来分析均摊时间复杂度
对一个数据结构进行连续的操作如果大多数情况下的时间复杂度比较低只有极端情况下时间复杂度很高而且这些操作在时序上存在前后连贯的关系。那么此时就可以将比较耗时的那个操作均摊给大多数低的时间复杂度的操作上。
而且一般可以用均摊时间复杂度分析的情况均摊时间复杂度就等于最好情况时间复杂度
4、总结
上面学习了四种时间复杂度的分析。但是一般来说平均时间复杂度用的很少均摊时间复杂度用的就更少。而且均摊时间复杂度实际上是一种特殊的平均时间复杂度。
所以不必纠结到底用什么复杂度来分析问题根据实际问题需要实际分析。对于一段代码如果它的时间复杂度在不同情况下量级不同可以采用不同的方法进行对比分析。其中最好最坏时间复杂度比较好分析平均时间复杂度与均摊时间复杂度比较难分析。
但是对于平均和均摊。他们实际是一个意思都有平均的意思。当出现O1操作的多于On操作的时候平均和均摊时间复杂度就都是O1。 这是一种感觉。一般情况下我们都可以感觉对而不用实际的计算。
本文是自己学习极客时间专栏-数据结构与算法之美后的笔记总结。如有侵权请联系我删除文章。
学习探讨加个人免费送技术书籍PDF电子书 qq1126137994 微信liu1126137994
