时间复杂度（带有元素列表）

出于好奇。假设我有一个包含N个元素（将重复）的列表以及一个将返回这些元素频率的函数。我认为这个计划的时间复杂性应该是O（N）是对的？由于函数只需循环遍历N并检查元素是否已经存在，如果是，+ =，else = 1。好的，所以我和我的朋友有一个论点，如果我们需要多元化它的频率呢？也许除以它的总数？我的朋友认为复杂度应该是O（N^2），但它听起来并不适合我。你怎么看，为什么？时间复杂度（带有元素列表）

谢谢。

来源

2017-03-16 USER1223_T

这取决于你将如何记录的频率。如果你将使用一个数组，他们对于每个+ =你需要先找到前一个频率值，这个复杂度是二次的。但是，如果您维护一个散列表结构，平均访问时间是即时的，则复杂度将是线性的。

来源

2017-03-16 14:59:38 infiniteRefactor

如果我们使用哈希表，复杂度仍然是O（N）？即使列表数量巨大，并且需要将其频率（对于每个元素）也乘以？ –

如果项目数量巨大，您可以分配一个巨大的散列表，以便表扩大不是问题，并且散列冲突很少。如果您需要对结果进行额外计算，这是一个不同的问题，您应该更具体地说明您想要做什么。例如，如果要将频率与列表中的值相乘，则需要迭代散列表的键并将其与值相乘。这将是第二步，总复杂性仍然是O（N）。 – infiniteRefactor

我明白了，非常感谢你的明确解释！ –

时间复杂度（带有元素列表）

回答

相关问题