algorithm - 预处理静态数据结构的大 O 表示法

Question

据我了解，O(n) 将随着输入数据集的大小线性增长。

我感到很困惑，因为我有一个查询结构，它将键映射到一个预处理值列表，这些预处理值在结构初始化后永远不会改变。

如果我将 n 定义为输入，一个键数组。

def (arrOfKeys): 
    for key in arrOfKeys: # O(n) Iterating through the input.
        preprocessedList = getPreprocessedListDifferentForEachKey(key) # O(1) this list could have any number of elements.
        for anotherPreprocessedList in preprocessedList: # * <- O(n) or O(1)?
            for element in anotherPreprocessedList: # * <- O(n) or O(1)?
                ...

• 我不确定这个 O(1) 是因为它经过预处理还是 O(n) 因为列表的大小取决于输入是什么？

在最坏的情况下，这最终是 O(n^3) 还是有可能争论 O(n)？

Answer 1

这取决于，如果 preprocessedList(及其子数组)始终具有恒定长度，则您的 2 个内部循环的时间复杂度为 O(1)。但是，如果它们依赖于输入参数 arrOfKeys，它们每个都是 O(n)，因此 O(n) * O(n) = O(n^2)。

结合第一个循环，然后将其乘以时间复杂度 O(n)。

因此，如果每个内部循环都是 O(n) 的，那么它总共将是 O(n^3)

如果 preprocessedList 的长度是可变的，但不依赖于 arrOfKeys 的长度，你可以将它定义为 m 并说它是时间复杂度 O(m)。然后你可以说时间复杂度是 O(n*m^2)。

通常可以引入另一个符号来描述时间复杂度，只要您解释它们是什么以及它们与数据的关系。