本文详细探讨了确定性算法、随机算法的时间复杂度，包括插入排序、快速排序等经典算法。此外，介绍了分治算法的时间复杂度理论，如主定理和Akra-Bazzi定理，并讨论了常见时间复杂度与数据规模的关系。平摊分析方法，如记账法和势能方法，用于分析操作序列的平均性能。最后，阐述了严谨的时间复杂度概念，考虑了数值大小的影响。
目录
一，确定性算法
确定性算法的时间复杂度，一般有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(nlogn) 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
六，严谨的时间复杂度
简单理解的时间复杂度，把常见的运算（如乘法）等都当成1次运算。
但是实际上，如果2个数非常大（远超int64的）的话，乘法耗时也不小。
所以，更严谨的时间复杂度，是需要考虑数值大小的，而不仅仅考虑数据量规模。
1，问题规模
一般情况下，我们会把问题的输入规模抽象成若干变量，其中包含两类，一类是数值规模，一类是数据量规模。
如判断一个数n是不是素数，n的范围是...，这是数值规模，
而更常见的是数据量规模，如输入n个数，完成排序。
2，传统的时间复杂度
一般情况下，我们把时间复杂度表示成关于问题规模的表达式并分析其增长规律。
其中最常见的就是关于数值规模的表达式，或者关于数据量规模的表达式，少部分问题是关于数值规模和数据量规模（二者都有）的表达式。
这些，通通都属于传统的时间复杂度。
3，严谨的时间复杂度
（1）输入规模
一个问题的输入规模是保存输入所有数据所需要的bit位数。
比如一般情况下，问题的输入都是n个32位的整数，那么问题规模就是32n
但如果整数最大值是2^k，k有可能远大于32，那么问题规模就是kn
问题规模和输入规模的含义其实是差不多的，主要差别在于，传统的问题规模关注的是表达一个抽象问题所使用的变量，而严谨的输入规模关注的是表达一个问题的具体输入所使用的总比特数。
（2）时间复杂度
时间复杂度是一个关于输入规模的函数。
通常，我们把O（32n）简单化为O（n）
甚至把O（（32n）^3）简单化为O（n^3）
但是对于O（kn）的算法，不能简单化为O（n）
4，伪多项式时间复杂度
如果一个算法的传统时间复杂度是多项式时间，而严谨的时间复杂度是指数时间，那么它就是伪多项式时间。
例如，判断一个数（最大是n）是不是素数，简单算法的时间复杂度是O（n）
但是n=2^k，所以严谨的时间复杂度是指数时间的。
扫一扫
1727
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
