arrays - 在线性时间内迭代嵌套数组

Question

我知道如何做到这一点的唯一方法是嵌套循环。但这在 O(n^2) 时间内运行。我的导师告诉我，如果在一次面试中，我被要求解决一个问题，而我开始通过嵌套循环来解决问题，我应该停下来重新思考这个问题。显然，总有比 O(n^2) 更好的路线。我一直在考虑这个问题，无论我如何在谷歌上重新表述我的问题，我都找不到答案。可能吗？

Answer 1

显然，总有比 O(n^2) 更好的路线

我认为这显然是错误的。有些问题确实是 O(n^2)。除非有特定的语言功能可以以某种方式使问题更有效，否则 O(n^2) 是嵌套数组的最佳选择。