英文:
What's the real meaning of 'n' in complexity analysis
问题
就我所知，在大O符号表示法中，当我们得出某个算法的时间/空间复杂度为O(n)时，我们指的是实现该算法所需的时间和额外空间与我们将要处理的数据的“大小”之间是线性关系。而数据的“大小”指的是其原子元素的数量，在这种情况下，它们的值范围并不在我们的考虑范围内。
现在，假设我们要处理一些“字符频率”问题。输入字符串将仅包含英文小写字符。使用哈希表来解决这类问题非常直观。然而，我想使用一个有26个槽位的数组（即常数空间）来模拟一个哈希表。
由于数组的大小无论输入字符串有多长都是固定的，因此可以合理地说空间复杂度是O(1)。
然而，数组的大小仍然取决于输入数据的某些方面（在这种情况下是范围），尽管不是它的大小。因此，考虑到这一点，似乎我们不能说空间复杂度是O(1)。
那么，我的问题是，在复杂度分析中，“n”的真正含义是什么？在提到的情景中，空间复杂度是多少？
英文:
As far as I am concerned, in the big-O notation, when we conclude that the time/space complexity of a certain algorithm is, say, O(n), we are saying that the relationship between the 'size' of time and extra space we need to realise the algorithm and the 'size' of the data we will be dealing with is linear. And the 'size' of data is the number of its atomic elements, the range of their values is out of our concern in this scenario.
Now, assume that we are dealing with some 'character frequency' problem. And the input strings will consist of only English lowercase characters. It's very intuitive to use Hash Table to tackle such problems. However, I want to use an array with 26 slots(i.e., constant space) to stimulate a Hash Table.
Since the size of the array is fixed no matter how long the input string will be, it makes sense to say that the space complexity is O(1).
However, the size of the array is still dependent upon some aspects of the input data (the range, in this case), though not the size of it. So, given that, it seems like that we can not say the space complexity is O(1).
So, my question is, What's the real meaning of 'n' in terms of complexity analysis. And what's the space complexity in the mentioned scenario?
答案1
得分: 3
在复杂性分析中，变量'n'代表影响算法性能的输入属性。 'n'的具体含义取决于正在分析的算法、对输入的假设以及与问题领域或实现细节相关的其他因素。
例如，让我们来看排序算法。
对于归并排序算法，其时间复杂度为O(n log n)，'n'表示输入数组中的元素数量。
另一方面，在计数排序算法中，时间复杂度为O(n + k)。假设输入由自然数组成，'n'指的是输入元素的数量，而'k'表示输入元素中的最大可能值。
现在，让我们考虑矩阵相加。
如果我们假设要相加的两个矩阵是方阵，那么时间复杂度是O(n^2)，其中'n'表示矩阵的阶数。在没有这个假设的情况下，时间复杂度变为O(nm)，其中'n'和'm'分别表示矩阵的行数和列数。
正如所示，复杂性分析中'n'的含义取决于各种因素，如算法和输入属性。要进行彻底的复杂性分析，必须确定所有影响算法复杂性的输入因素并相应地指定它们。
在您的示例中，如果只使用26个英文字母，空间复杂度确实可以为O(1)，因为它是恒定的，您将始终为任何输入分配26个插槽。
但是，如果没有这个假设，空间复杂度可能为O(n)，其中'n'表示可能字符集中的元素数量，您可能会分配超过26个插槽。
此外，即使前面的假设成立，但如果输入字符串非常长并且必须保存在内存中，那么空间复杂度可能为O(n)，其中'n'表示输入字符串的长度。
英文:
In complexity analysis, the variable 'n' represents a property of the input that influences the algorithm's performance.
The specific meaning of 'n' depends on the algorithm being analyzed, the assumptions made about the input, and other factors related to the problem domain or the implementation details.
<hr/>
For instance, let's examine sorting algorithms.
In the case of the Merge Sort algorithm, which has a time complexity of O(n log n), 'n' signifies the number of elements in the input array.
On the other hand, in the Counting Sort algorithm, the time complexity is O(n + k).
Assuming the input consists of natural numbers, 'n' refers to the number of elements in the input, while 'k' represents the maximum possible value among the input elements.
<hr/>
Now, let's consider matrix addition.
If we assume that the two matrices being added are square, the time complexity is O(n^2), where 'n' denotes the order of the matrix. Without this assumption, the time complexity becomes O(nm), with 'n' and 'm' representing the number of rows and columns in the matrices, respectively.
<hr/>
As demonstrated, the meaning of 'n' in complexity analysis relies on various factors such as the algorithm, and input properties.
To conduct a thorough complexity analysis, it is crucial to identify all input factors that impact the algorithm's complexity and specify them accordingly.
<hr/>
In your example, the space complexity can be indeed O(1) under the assumption that only the 26 English alphabets are used since it is constant and you will always allocate 26 slots for any inputs.
However, without this assumption, the space complexity could be O(n), where 'n' represents the number of elements in the set of possible characters and you could allocate more than 26 slots.
Also, even if the previous assumption holds, but if the input string can be very long and must be saved in the memory, then the space complexity could be O(n), where 'n' represents the length of the input string.
答案2
得分: 0
关于算法的复杂性陈述是为了传达这些算法的重要性能特性。
你可以使用任何你喜欢的变量来进行这些陈述。
例如，如果你要编写一个针对小写字母的正常的“最常见字符”算法，你通常会说它花费O(n)的时间和O(1)的空间。你可以指定n是字符串的长度，但你不需要，因为那是一个显而易见的选择。当不明显时，你需要指定以进行传达。
如果你要编写相同的算法，但接受无限制的Unicode字符串，那么你可能会说它花费O(k)的空间，其中k是所使用的字母表的大小。你可以仍然说它花费O(1)的空间，但这会无法传达关于其内存消耗可能在实践中很重要的信息。
当你对复杂性陈述的唯一用途是在考试中回答问题时，很容易忘记它们在实际评估算法的实际目的中的重要性。
英文:
Statements of complexity are made about algorithms to communicate important performance properties of those algorithms.
You can make those statements in terms of whatever variables you like.
If you were to write the normal "most frequent character" algorithm for lowercase letters, for example, then you would normally say that it takes O(n) time and O(1) space. You could specify that n is the length of the string, but you wouldn't need to, because that's the obvious variable to choose. When it's not obvious, you do need to specify in order to communicate.
If you were to write the same algorithm, but accepting unrestricted Unicode strings, then you would probably say that it takes O(k) space, where k is the size of the alphabet used. You could still say it takes O(1) space, but that fails to communicate information about its memory consumption that could be important in practice.
When the only use you've had for complexity statements is answering questions on tests, it's easy to forget their real-life purpose in the practical evaluation of algorithms.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论