识别运行频率函数的时间复杂度（大o）？

Question

我编写了一个非常基本的函数，可以为给定列表生成频率：

myList = ['hello', 'apply', 'big', 'apple', 'tall', 'apply'] --input

myList = [('hello', 1), ('apply', 2), ('big', 1), ('apple', 1), ('tall',1)] --output

我的函数：

frequency :: (Eq a) => [a] -> ([(a, Int)] -> [(a, Int)]) -> [(a, Int)]
frequency li removeDup = removeDup $ map (\el -> (el, indexes el)) li
   where
      indexes el = length $ findIndices (== el) li

removeDuplicates :: (Eq a) => [(a, Int)] -> [(a, Int)]
removeDuplicates [] = []
removeDuplicates ((x1, x2) : xs) = (x1, x2) : removeDuplicates (filter (\(y1, y2) -> x1 /= y1) xs)

我正在尝试计算函数的运行时间复杂度。我最初的想法是它的 O(n) 因为我首先获得 'indexes' 值，然后映射并最终过滤。

这个结论对吗？
是否有执行相同功能的 O(1) 方法？

Answer 1

我假设您将 removeDuplicates 传递给 frequency 并使用您的代码的这个稍微修改的版本：

frequency :: (Eq a) => [a] -> [(a, Int)]
frequency li = removeDuplicates $ map (\el -> (el, indexes el)) li
    where
    indexes el = length $ findIndices (== el) li

removeDuplicates :: (Eq a) => [(a, Int)] -> [(a, Int)]
removeDuplicates [] = []
removeDuplicates ((x1, x2) : xs) =
    (x1, x2) : removeDuplicates (filter (\(y1, y2) -> x1 /= y1) xs)

让我们看看frequency的每个部分在做什么：

map (\el -> (el, indexes el)) li

正如您所提到的，map f li 原则上在列表 li 的长度中是 O(n)。然而，这仅在 f 的复杂性不依赖于 li 的情况下成立。因此，我们需要仔细检查映射的函数：

\el -> (el, indexes el)

代入indexes的定义，我们得到：

\el -> (el, length $ findIndices (== el) li)

findIndices是list的长度O(n)，因为要对每一个元素都进行测试，所以这个函数的复杂度至少是O(n) 在 li 的长度。 length 在列表的长度上也是线性的，这意味着在最坏的情况下（即当所有元素都等于 el 时）它也会是 O(n ) 的长度为 li。鉴于 findIndices 已经是 O(n)，长度不会影响整体复杂度。最后，创建对，这是最后一步，是常数时间且没有问题。

因此我们可以得出结论\el -> (el, indexes el)在li的长度上是O(n)。既然如此，map (\el -> (el, indexes el)) li 在 li 的长度上实际上是 O(n^2)，因为它执行 O(n) 操作 n 次。

removeDuplicates

让我们关注递归的情况：

(x1, x2) : removeDuplicates (filter (\(y1, y2) -> x1 /= y1) xs)

这里的关键操作是过滤，在xs的长度上是O(n)。每个 li 的元素进行一次过滤。现在，即使 xs 随着我们向列表末尾移动而变短，xs 的平均长度与 li 的长度成正比。既然如此，我们将再次执行 O(n) 操作（长度为 li）n 次，这意味着 removeDuplicates 是 O(n^2) —— 就像 Data.List 中的 nub。（得出相同结论的另一种方法是注意到 removeDuplicates 将每个元素与其他所有元素进行比较，从而导致 n*(n-1)/2 比较。）

frequency li = removeDuplicates $ map (\el -> (el, indexes el)) li

frequency 由一个 O(n^2) 操作和另一个 O(n^2) 操作组成;因此，列表的长度是 O(n^2)。

Is there a O(1) method of performing the same function?

O(1) 是不可能的，因为无法回避需要对 做一些事情 列表的元素。不过，肯定有可能比 O(n^2) 做得更好。例如，通过对列表进行排序，您可以避免将每个元素与所有其他元素进行比较（在 map (\el -> (el, indexes el)) li 和 removeDuplicates 中都会发生），因为在排序列表中，只有彼此相邻的元素可能等于。举个具体的例子，这个函数...

group . sort

... 是 O(n*log(n))（来自 Data.List 的 sort 是 O(n* log(n))，而 group 是 O(n)，因为它只需要将每个元素与下一个元素进行比较）。

P.S.: 这可能与你想要做的事情无关，但对于完全不同的事情，你可能想尝试使用 dictionary 来跟踪计数。这将使有效的线性 frequency 成为可能，如果您需要处理大型输入列表，这应该在性能方面有所回报。

识别运行频率函数的时间复杂度（大o）？

Identifying run time complexity (big o) of frequency function?

big-o

haskell