使用两个不同定义的对称差异的运行时复杂性应该是等效的吗？

Question

对称差有两个在数学上等价的定义，我有 3 个函数可以构成对称差，但是当我尝试用这两个定义求总复杂度时，我得到了两个不同的表达式。

这些是函数的运行时间：

int minus(int a[], int b[])    //O(alogb)//here a and b denotes the size of the arrays
int union(int a[], int b[])    //O(a+b)
int intersect(int a[], int b[])//O(alogb)//a is the smaller array WLOG

使用对称差分的第一个定义（并集 b）-（a 相交 b）：

伪代码：

int xor(int a[], int b[]){
    u = union(a,b);
    i = intersect(a,b);
    minus(u,i);
}

因此运行时复杂度为：O(a+b+alogb+(a+b)log(alogb))

使用其他定义 (a-b)union(b-a):

int xor(int a[], int b[]){
    m1 = minus(a,b);
    m2 = minus(b,a);
    union(m1,m2);
}

所以这次的运行时间是O(alogb+bloga+alogb+bloga)=O(2(alogb+bloga))

如您所见，尽管我尝试在两个表达式中都放置数字并且结果非常接近，但它们完全不同。

我的问题是，这两个复杂性不应该是相同的吗？因为它们应该是等价的？

Answer 1

不，仅仅因为两个算法是等价的（在定义它们的域上产生相同的结果）并不意味着它们将具有相同的运行时间复杂度。例如，我可以使用通常的 B 进制乘法算法 (O(n^2)) 来计算两个整数的倍数，或者我可以使用 Karatsuba 算法，其复杂度为 (O(n^k);k 大约。 1.59)...两者都产生相同的结果，因此是等价的，但一个在渐近线中更快。

也就是说，你没有理解大 O 符号。这实际上是低阶项消失的限制，因此滥用符号 O(2a^2) = O(a^2) = O(a^2+a) 等。对于上述两种方法，只需写 O( n*log(n)) - 它们具有相同的渐近复杂度。

使用两个不同定义的对称差异的运行时复杂性应该是等效的吗？

Is the runtime complexity of symmetric difference using two different definitions supposed to be equivalent?

performance

function

runtime

big-o

time-complexity