英文:
What is time complexity for a nested for loop where the inner loop is for a different array?
问题
如果我们正在衡量一个数组的时间复杂度，是否可以在时间复杂度计算中忽略另一个数组？（即，如果我们只关心外部数组的增长，是否可以表示为O(N)，还是必须给出总体时间复杂度O(N*M)。）
for (int i = 0; i <= n.size(); ++i) {
// 外部循环体内的代码
for (int j = 0; j <= m.size(); ++j) {
// 外部和内部循环体内的代码
}
}
英文:
If we are measuring time complexity for one array can we disregard a different array in our time complexity calculation? (ie. if we only care about the outer array's growth could I say O(N) or do I have to give time complexity overall O(N*M).
for (int i = 0; i <= n.size(); ++i) {
// codes inside the body of outer loop
for (int j = 0; j <= m.size(); ++j) {
// codes inside the body of both outer and inner loop
}
}
答案1
得分: 1
这可能会忽略其中一个循环，如果该循环的数组大小是固定的。如果不是这种情况，那么您将考虑两者，并将整个算法的复杂度表示为O(n*m)。
英文:
It might be ok to ignore one loop or the other if the array size for that loop is fixed. If that's not the case, then you'd take both into account and state the complexity for the whole algorithm as O(n*m).
答案2
得分: 1
如果我们正在对一个数组的时间复杂度进行测量，是否可以在我们的时间复杂度计算中忽略另一个不同的数组？
是的，当且仅当这个不同的数组是一个常数大小的数组。
如果所讨论的数组是唯一与输入大小n成比例增长的数组，这意味着另一个数组是一个常数大小的数组，而渐近分析中的常数因子会被忽略。因此，您最终得到O(n)的时间复杂度。
然而，如果另一个数组的大小不是常数，并且它根据输入大小变化，那么应该计算相应的相关性（它如何根据输入变化）并将其乘以T=O(n)。
需要注意的是，您的措辞：
如果我们正在对一个数组的时间复杂度进行测量
并不完全正确，因为您并不是为一个数组、列表或任何其他数据结构计算时间复杂度，per se；相反，您是在为您的算法计算时间复杂度，这可能涉及不同的数据结构、结构和操作。
英文:
>If we are measuring time complexity for one array can we disregard a different array in our time complexity calculation?
Yes, IFF the different array is of a constant size.
If the array in question is the only one that grows proportionally to the input size n, this implies, that the other array is of a constant size, and the constant factors are disregarded in the Asymptotic Analysis. So, you will end up with O(n) time complexity.
If, however, another array is not of a constant size and it changes according to the input size, then the corresponding correlation (how it changes based on the input) should be calculated and multiplied by T=O(n).
Note, that your wording:
>If we are measuring time complexity for one array
is not quite correct, as you don't calculate the Time Complexity for an array, list, or any other data structure, per se; rather you calculate it for your algorithm, which might involve different data structures, constructs, and operations.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论