令 m 为数组 A 的大小，n 为数组 B 的大小。以下 while 循环的复杂度是多少？
while (i<n && j<m){ if (some condition) i++ else j++}
- 数组示例:A=[1,2,3,4] B=[1,2,3,4] while 循环最多执行 5+4 次 O(m+n)。
- 数组示例:A=[1,2,3,4,7,8,9,10] B=[1,2,3,4] while 循环最多执行 4 次 O(n) .
我无法弄清楚如何表示 while 循环的复杂性。
最佳答案
一种常见的方法是描述最坏情况时间复杂度。在您的示例中，最坏情况下的时间复杂度是 O(m + n)，因为无论什么某些条件是在给定的循环迭代期间，循环迭代的总数最多为m + n。
如果强调时间复杂度在某些情况下具有较小的上限很重要，那么您需要弄清楚这些情况是什么，并找到一种表达它们的方法。 (例如，如果给定算法采用大小为 n 的数组，并且最坏情况 O(n2) 时间，也可以将其描述为“O(mn) 时间，其中 m 是 的数量数组中的不同值”——当然，只有当这是真的时——我们引入了一个额外的变量 m 来让我们捕捉更多与更少对性能的影响重复值。)
关于algorithm - 这个 while 循环的复杂性是什么？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/54896128/