我的代码是快速查找算法的一个实现，我通常认为我的代码是为了理解理论问题
#include <stdio.h>
#define N 10000
main() {
int i, t, p, q, id[N];
for (i = 0; i < N; i++)
id[i] = i;
printf("Input pair p q: ");
while (scanf("%d %d", &p, &q) == 2) {
if (id[p] == id[q])
printf("%d %d already connected\n", p,q);
else {
for (t = id[p], i = 0; i < N; i++)
if (id[i] == t)
id[i] = id[q];
printf("pair %d %d not yet connected\n", p, q);
}
printf("Input pair p q: ");
}
}字符串
假设图12-6，2-3，0-9，5-4，3-10，10-8中有N个顶点，有k对，快速查找用于查找操作，在线连通性算法将执行多少查找操作？**O（kN）Θ（kN）O（k）Θ（k）**这将帮助我找到操作的数量。我知道find操作的单位成本是O（1），因为我们需要它做的就是指向另一个数组。但当我考虑到一定数量的对子时，我就糊涂了。
我开始学习这种复杂性分析，符号让我感到困惑，因为我知道大teta是紧密结合的，并且比大O更精确地表达复杂性分析，但对于寻找许多操作的情况，我只是不明白哪一个更适合。
1条答案
按热度按时间l2osamch1#
有两个合理的问题维度，可以考虑程序的渐近复杂性：节点数
N和查询数k。考虑这些常数中的任何一个（不管它的值是什么）意味着它从复杂性分析中排除，因为渐近复杂性是关于程序行为的一些度量如何随着问题大小的变化而变化。我将根据表达程序的C语言的抽象机器语义来考虑这两个维度上的缩放：id数组，而不管查询的数量。id[p] == id[q]，则查询需要Θ（1）步（a * 类型1* 查询）。id值的数量减少至少1。最初有N个不同的id值，并且该数量不能减少到1以下，因此最多N查询可以是这种类型。N-1）* O（N）= O（N2）限定。（N-1个查询，每个查询需要O（N）步）。N查询列表，这些查询总共需要Ω（N2）步，因此没有更严格的上限。N-2，N-1;N-3，N-1;...; 0，N-1.每个查询将从0迭代到p，总共（N-1）*N/2次迭代。这给了我们：
| 奥|说明| Explanation |
| --|--| ------------ |
| 不适用|设置| setup |
| k|类型1查询| type 1 queries |
| 氮气|类型2查询| type 2 queries |
| k + N + N2|总计| total |
| k + N2|标准简化形式| standard reduced form |
k个查询，所以这是查询的总贡献的更好的下限，而不是1+1 = 2。我开始学习这种复杂性分析，符号让我感到困惑，因为我知道大teta是紧密结合的，并且比大O更精确地表达复杂性分析，但对于寻找许多操作的情况，我只是不明白哪一个更适合。
“更紧密地结合”是对大Theta的一个潜在的误导性描述。Θ与0之间的差异在于0仅提供上限，而Θ提供上限和下限两者。在这种情况下，我们不应该忽略大Ω（Ω），它只提供了一个下限。你总是可以表达一个给定函数的上（O）和下（Ω）渐近界，但并不总是可以表达一个有用的双侧界。
因此，通常从计算big-O开始。这并不是唯一的，但人们通常会试图找到尽可能紧的边界。上面的分析通过表明不可能有比所发现的更紧的标准形式上限来解决上限的紧性。
有时通过计算大-Ω来继续。这对于考虑是否存在算法更有效的输入类别是有用的。例如，插入排序在平均和最坏情况下需要O（N2）步，但总体上是Ω（N），因为它在线性时间内对已经近似有序的输入进行排序。
如果可以找到一个方便的函数形式，可以作为大O和大Ω，那么这也是一个有用的大Θ。如果不是，则通常忽略大-Θ。例如，我们总是可以说f（N）是Θ（f（N）），但我们通常不会这样做，因为这不会给予我们任何有用的信息。