数不出来。O(n)中的词语

Question

我是来面试的。还有一个面试问题我很难回答。

“玫瑰就是玫瑰”写一种算法，打印一个字符/单词发生的次数。例如，a-3玫瑰-3是-2 还要确保在打印结果时，它们是按照原来句子中的内容排列的。这一切都是为了n，。

我得到了答案，每一个单词出现的次数按顺序排列，就像原来句子中的那样。我用Dictionary<string,int>做的。然而，我不明白“n”是什么意思，这是我需要你们解释的。

Answer 1

有26个字符，所以可以使用counting sort对它们进行排序，在计数排序中，可以有一个索引来确定首次访问特定字符的时间，以保存发生顺序。它们可以按照它们的计数和它们的出现来排序，就像基数排序一样。

编辑:根据单词第一件事，每个人都能想到它，就是使用哈希表并在散列中插入单词，这样就可以计数它们，并且它们可以在O(n)中排序，因为所有的数字都在1.n钢内，所以可以通过在O(n)中计数排序来对它们进行排序，对于它们的出现，也可以遍历字符串并更改相同值的位置。

Answer 2

N的顺序意味着您只遍历字符串一次或n的较小倍数，其中n是字符串中的字符数。因此，存储字符串及其出现数的解决方案是O(n)，顺序为n，因为您只循环了整个字符串一次。但是，它以您创建的列表的形式使用额外的空间。

Answer 3

阶N指的是大O计算复杂性分析，在这里你得到了算法的一个很好的上限。这是我们早期在数据结构课中讨论的理论，所以我们可以折磨，我的意思是，当我们以平衡的方式遍历时，帮助学生获得便利，各种不同的知识树，都不一样。在您的情况下，他们希望您的算法在计算时间上与文本的大小成比例增长。