时间复杂度
目录
一，确定性算法
确定性算法的时间复杂度，一般有2个维度：好坏情况，上下界
1，已知数组中有且仅有一个负数，找到这个负数
采用枚举法，代码：
-
int findNegative(vector<int>v)
-
{
-
for (int i = 0; i < v.size(); i++)if (v[i] < 0)return v[i];
-
return 0;
-
}
最好情况：一次找到
最坏情况：最后一次才找到
平均情况：找了一半元素才找到
| 时间复杂度 |
渐进下界Ω |
渐进上界O |
渐进确界θ |
| 最好情况 |
1 |
1 |
1 |
| 最坏情况 |
n |
n |
n |
| 平均情况 |
n |
n |
n |
2，插入排序
| 时间复杂度 |
渐进下界Ω |
渐进上界O |
渐进确界θ |
| 最好情况 |
n |
n |
n |
| 最坏情况 |
n^2 |
n^2 |
n^2 |
| 平均情况 |
n^2 |
n^2 |
n^2 |
插入排序的最坏情况下，渐进下界为Ω（n^2），也可以说是Ω（n）
渐进上界为O（n^2），也可以说是 O（n^3）
3，快速排序
快速排序的好坏平均，其实是分2个维度，一个是数列中元素和元素重复的程度，一个是分治划分的均匀程度。
| 时间复杂度 |
渐进下界Ω |
渐进上界O |
渐进确界θ |
| 最好情况 |
n logn |
n logn |
n logn |
| 最坏情况 |
n^2 |
n^2 |
n^2 |
| 平均情况 |
n logn |
n^2 |
/ |
如果限定所有元素都互不相同，那么好坏平均只涉及分治划分的均匀程度，那么渐进确界为O（n logn）
二，随机算法
随机算法的好坏平均，分2个维度，一个是问题需要处理的数据的好坏，一个是算法本身采用的随机数的好坏。
快速排序选取划分节点的这一步，可以随机选一个，也可以固定选待排序段的第一个元素，本质上是一样的，所以也可以说快速排序也是一种随机算法。
1，已知数组中有且仅有一个负数，找到这个负数
不断随机尝试，代码：
-
int findNegative(vector<int>v)
-
{
-
while (true) {
-
int i = rand() % v.size();
-
if (v[i] < 0)return v[i];
-
}
-
}
假设rand函数的随机数范围足以覆盖v.size()的大小。
最好情况：一次找到
最坏情况：永远找不到
平均情况：尝试次数的均值恰好是n
| 时间复杂度 |
渐进下界Ω |
渐进上界O |
渐进确界θ |
| 最好情况 |
1 |
1 |
1 |
| 最坏情况 |
∀ |
无 |
无 |
| 平均情况 |
n |
n |
n |
2，已知数组中存在负数，找出任意一个负数
算法同上，代码不变。
数据的最好情况：全都是负数
数据的最坏情况：只有一个负数
数据的平均情况：恰好有一半是负数
| 时间复杂度 |
算法最好情况 |
算法最坏情况 |
算法平均情况 |
| 数据最好情况 |
θ（1） |
θ（1） |
θ（1） |
| 数据最坏情况 |
θ（1） |
Ω（∀） |
θ（n） |
| 数据平均情况 |
θ（1） |
Ω（∀） |
θ（1） |
PS：
恰好有一半是负数时，尝试次数的均值恰好是2，所以是θ（1）
三，分治算法的时间复杂度
1，主定理的简化版本
考虑形如
的递归式，
- 如果，那么；
- 如果，那么；
- 如果，那么。
2，主定理
主定理是用来求分治算法的时间复杂度的公式定理。
分析：
这个递推式其实不难求解，就是高中数学里面的数列递推式，做个n = b^t 的代换即可，后面就是三种类型的级数求和、对数的换底公式。
(3)中，其实前半句所描述的条件可以省略，因为 af(n/b) <= cf(n) 就包含了 f(n) = Ω（n^...）这个条件。
3，Akra-Bazzi定理的简化版本
4，Akra-Bazzi定理
5，Leighton定理
四，常见时间复杂度和数据规模
ACM里面，常见的时间复杂度和数据规模的对应关系：
O(n^2) n=10^3-10^4
O(nlong) n=10^4 - 10^6
O(n) n=10^6 - 10^8
O(sqrt(n)) n=10^8 – max_int
O(log n) n=10^8 – max_int
五，平摊分析
1，平摊分析
平摊分析指的是一系列操作执行的平均时间。
和平均情况下的时间复杂度不同，平摊分析指的是最坏情况下，一系列操作的平均时间。
例如：
-
int x[100];
-
-
void out(int id)
-
{
-
if(id==88)for(int i=0;i<100;i++)cout<<x[i];
-
}
-
-
void out2()
-
{
-
for(int i=0;i<100;i++)out(i);
-
}
首先，out函数在最坏情况下是O（n），在平均情况下是O（1）
其次，out2函数在平均情况下是O（n），这几个都是毫无疑问的。
那么out2函数的最坏情况呢？
在不知道out函数的内部实现的情况下，只知道out函数在最坏情况下是O（n），在平均情况下是O（1），我们对out2函数的最坏时间复杂度的评估只能是O（n^2）
但是在知道out函数的内部实现之后，我们发现out2的最坏时间复杂度是O（n）
所以，我们可以把out函数在平均情况下是O（1）表述成，n次调用out函数的平摊时间复杂度是O（1）
2，聚集分析
聚集分析指的是，要求平摊性能，可以先求n个操作的总时间T(n)，然后就能得到平摊时间T(n)/n
（1）栈操作
假设push和pop的时间都是O（1），考虑一个新操作multiPop，它可以一直执行pop操作直到清空栈
如果有n个操作，每个操作都是push、pop、multiPop中的一个，初始栈是空的，
那么multiPop的时间复杂度是O（n），因为最多只有n-1个元素可以弹出
然而n次操作的平摊时间是O（1），因为其中所有multiPop操作的弹出元素数目总和不会超过n-1
（2）二进制计数器
一个k位的整数初始值为0，执行n次加1操作，会有多少次进位呢？（n<2^k）
比如1到2是1次进位，11到12是2次进位。
单次操作最多有k次进位，但单次操作的平摊时间是O（1）
3，记账方法
记账方法是给每种操作赋予一个平摊代价，这个值可能大于也可能小于实际代价，我们把平摊代价大于实际代价的部分，称为存款。
但是根据平摊代价计算出来的总代价，一定不低于实际总代价。
（1）栈操作
以栈为例，我们分别赋予push、pop、multiPop平摊代价2、0、0
那么据此算出来的总代价上限是2n，即O（n），而实际总代价的上限是2n-2，即O（n）
（2）二进制计数器
把一位上的0变成1的子操作赋予平摊代价2元，把1变成0的操作赋予平摊代价0元，
0变成1的时候，1元是实际代价，1元是存款，所以每一位值为1的位上都有1元存款，所以1变成0的时候只需要存款即可，这样，总平摊代价就不低于实际总代价。
这样，单次操作的平摊代价就是2了，即O（1）
4，势能方法
势能方法就是给整个状态赋予一个数，叫做势能，或者势。
把平摊代价表示为实际代价加上势能的增量，那么总平摊代价减去实际总代价就等于最终势能减去初始势能。
所以要想总平摊代价不低于实际总代价，就需要任何时刻的势能都不低于初始势能。
（1）栈操作
用栈中的元素个数，表示整个栈的势能。
那么，push、pop、multiPop的平摊代价分别为2、0、0
（2）二进制计数器
用位值为1的个数，表示整个计数器的势能，
那么，单次操作的平摊代价就是2
5，动态表
按照平摊性能的思路，考虑如何设计动态表的扩张和收缩。
假设单次插入和删除操作是O（1），只需要考虑扩张和收缩如何设计。
（1）动态表扩张
扩张的设计比较简单，表的元素个数达到预留空间大小时，就分配一个新的空间，大小翻一倍，然后把元素全部copy过去。
这样，单次插入操作的平摊性能是3
（2）动态表扩张和收缩
如果表的收缩采取类似的措施，当装载因子低于1/2的时候，就分配一个新空间，大小为原来的一半，那么就有可能，元素个数在分界线处不断徘徊，就需要不断扩张和收缩，时间复杂度很高。
所以，收缩的阈值必须更低。
以1/4为例，每次当装载因子低于1/4时，就分配一个新空间，大小为原来的一半。
那么，一些列扩张和收缩操作的平摊性能还是3
文章来源: blog.csdn.net，作者：csuzhucong，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/nameofcsdn/article/details/115269383
- 点赞
- 收藏
- 关注作者
评论（0）