算法复杂度时间 [英] Algorithm Complexity Time

问题描述

我目前遇到了问题识别和理解以下算法的复杂性时。

I am currently having trouble identifying and understanding the complexity time of the following algorithm.

背景：有文件的列表，每个包含候选ID的列表。既，文件和在其中的候选的数目的数目是不固定的。

Background: There is a list of files, each containing a list of candidate Ids. Both, number of files and number of candidates within them are not fixed.

您将如何计算的算法负责的时间复杂度： 读取每个文件并添加所有的独特候选ID转换成HashSet的？

How would you calculate the time complexity for an algorithm which is responsible for: Reading each file and adding all the unique candidate Ids into a Hashset?

感谢。

推荐答案

我只是重复什么阿​​米特说，请给他upvote如果这是清楚你 - 我发现的解释有点混乱。

i'm just repeating what amit said, so please give him the upvote if that is clear to you - i find that explanation a bit confusing.

一般的复杂度为O（n），其中n为考生总人数（所有文件）。所以如果你有 A 文件，每个文件 B 候选人则所花的时间是成正比的 A * B 。

your average complexity is O(n) where n is the total number of candidates (from all files). so if you have a files, each with b candidates then the time taken is proportional to a * b.

这是因为为您解决问题最简单的方法是简单地遍历所有的数据，将其添加到组。该集将丢弃重复是必要的。

this is because the simplest way to solve your problem is to simply loop through all the data, adding them to the set. the set will discard duplicates as necessary.

遍历所有的值需要的时间与值的数量（即是O（n）的部分）。增加值到哈希集合时间是固定的（或O（1））。因为这是每个条目固定的时间，你的总​​时间仍然为O（n）。

looping over all values takes time proportional to the number of values (that is the O(n) part). adding a value to a hash set takes constant time (or O(1)). since that is constant time per entry, your overall time remains O(n).

然而，散列集有一个奇怪的最坏的情况下的行为 - 它们需要时间成比例的内容中的一些（异常）的情况下的尺寸。因此在非常最坏的情况下，每次添加一个值时，它需要O（米）的工作量，其中m是在该组中的条目数。

however, hash sets have a strange worst case behaviour - they take time proportional to the size of the contents in some (unusual) cases. so in the very worst case, each time you add a value it requires O(m) amount of work, where m is the number of entries in the set.

现在m为（约 - 它开始于零和上升到...）不同值的数目。所以我们有两个常见的情况：

now m is (approximately - it starts at zero and goes up to...) the number of distinct values. so we have two common cases:

• 如果数量的不同的的考生增加，因为我们读更多（如此，例如，90％的文件是不断有新的候选人），则M N成正比。这意味着，将每名候选人的工作，增加比例为n。这样的总的工作是成正比的N ^ 2（因为每名候选人，我们做的工作比例为n，并有n个候选人）。因此，最坏的情况是O（n ^ 2）。

• if the number of distinct candidates increases as we read more (so, for example, 90% of the files are always new candidates) then m is proportional to n. that means that the work of adding each candidate increases proportional to n. so the total work is proportional to n^2 (since for each candidate we do work proportional to n, and there are n candidates). so the worst case is O(n^2).

如果的的不同的的候选人实际上是固定的号码，然后当你读到越来越多的文件，他们往往只是充满已知的候选人。在这种情况下，插入到集合中的额外的工作是恒定的（你只得到了奇怪的行为的固定次数的的唯一的候选人 - 它不依赖于N）。在这种情况下，该组的表现并不让越来越差为n变大，因此最坏的情况下复杂度仍然为O（n）。

if the number of distinct candidates is actually fixed, then as you read more and more files they tend to be just full of known candidates. in that case the extra work for inserting into the set is constant (you only get the strange behaviour a fixed number of times for the unique candidates - it doesn't depend on n). in that case the performance of the set does not keep getting worse as n gets larger and larger, so the worst case complexity remains O(n).

这篇关于算法复杂度时间的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！