数据集滤波算法的时间复杂度估计

Question

美好的一天...

我目前正在研究非常特定的几何数据集的滤波算法，而且我对如何估计其时间复杂度感到很遗憾。从概念的角度来看，我理解时间复杂度是作为n的函数估计的，n是算法的输入大小。让我简要描述一下我的算法：

算法的输入数据是初始数据集和要应用于该数据集的一组过滤器。因此，在每个步骤中，算法迭代数据集的所有元素并将过滤器应用于数据集的每个元素，然后决定是否应该从数据集中删除此类元素，等等......

我的问题是：（I）我觉得应该将n定义为数据集中的元素数量，但是我遗漏了一个重要因素：要应用的过滤器数量。为了时间复杂度估计的目的，我如何考虑算法输入数据中的滤波器数量？

（II）由于我不知道先验在每个滤波器中将删除多少个元素，我如何计算算法作为n的函数执行的操作数？

（III）每个滤波器都是我算法调用的独立程序，为了计算算法的时间复杂度，我是否应该考虑每个滤波器的时间复杂度？如果过滤器是用户定义的，并且它们的复杂性不能事先知道，会发生什么？

感谢您对此问题的任何澄清或线索......

问候。

Answer 1

我不是时间复杂的专家，但我可以尽力帮助你。

如果我理解正确，您的算法会对数据应用N个过滤器，可能每次都会减少数据。每个过滤器都线性应用于数据集的每个元素。我们将研究最坏情况的复杂性，因为它更容易计算/理解。

我们用符号表示：

n：应用过滤器1之前的数据集长度。由于您的过滤器只能减小数据集的大小，因此最坏的情况是没有过滤器减少数据集，即每个过滤器都应用于n个元素。

T：算法的复杂性

Ci：第i个过滤器的复杂性。因为我不知道你使用什么样的数据我真的不能更精确。

M：过滤器数量

所以我们有：

T（n，M）= nC1 + nC2 + ... + n * CM

现在你不知道过滤器的复杂程度，我们不能更深入，因为它可以变化很大。例如，如果过滤器应用于整数并且只是一个阈值，则复杂度为O（1）但如果要测试数字a是否为素数，则是O（log（a）^ 6）...

但是如果你可以估算所有滤波器C_worst中最差的复杂度，那么使用大哦符号我们可以估算：

T（n，M）= O（MnC_worst）

关于整数的示例：如果a是数据集的最大值，并且最差复杂度过滤器在整数输入中是线性的，则我们得到T（n，M，a）= O（Mna）