如何使用数学或大O表示法计算数据代数中使用的代数操作的时间复杂度。我将用书中的例子来解释我的问题。考虑一下书中给出的例子。B

在上面的例子中,我想计算转置和合成操作的时间复杂度。
如果可能的话,我还想找出其他代数数据操作的时间复杂度。如果你需要更多的解释,请告诉我。
@wesholler我编辑了我的问题以理解您的解释。下面是一个真实的例子,假设我们想要计算下面使用的操作的时间复杂度。
假设我有如下的数据操作代数

你能描述一下我们如何计算上面例子中的时间复杂度吗?最好是在大O区?
谢谢
发布于 2015-10-08 07:50:02
这个答案分为三个部分:
一般时间复杂度分析
通常,时间复杂度/BigO可以通过考虑操作的起源来确定-也就是说,哪些操作是从更多的本原代数扩展而来的?
下面的规则描述了扩展到幂集代数中的一元和二元运算的时间复杂度的上界。


一元扩展可以被认为类似于map操作,因此具有线性时间复杂度。二进制扩展计算操作参数的叉积,因此具有类似于O(n^2)的最坏情况下的时间复杂度。然而,重要的是要考虑到真正的上限是两个参数的基数的乘积;在实践中,当组合或超限制操作的右侧参数是单例时,经常会出现这种情况。
代数库实现的时间复杂度
我们可以看几个扩展如何影响时间复杂度的例子,同时分析algebraixlib实现的复杂性(最后一部分讨论其他实现)。
因为它是数据代数的参考实现,所以algebraixlib确实实现了扩展操作。出于这个原因,下面使用Big Theta,因为公式既表示时间复杂度的下界,也表示时间复杂度的上限。
下面是从couplets扩展到relations,然后扩展到clans的一元操作transpose。

同样,这里是从couplets扩展到relations,然后扩展到clans的二进制操作compose。

很明显,这两个家族操作的复杂性都受到关系元素的数量以及这些关系中的对联数量的影响。
其他实现的时间复杂性
值得注意的是,上面的部分描述了特定于在algebraixlib中实现的算法的时间复杂度。
可以想象使用类似于排序-合并-连接或散列连接的方法来实现例如clans.cross_union。在这种情况下,上限将保持不变,但下限(和预期的)时间复杂度将降低一个或多个度数。
https://stackoverflow.com/questions/32972084
复制相似问题