1

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

4

2 回答 2

2

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

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

于 2013-03-15T00:41:58.370 回答
1

这是最快的方法。

如果您检查与整个嵌套数组结构中的条目一样多的条目......那么，您显然不能做得更好，不是吗？;)

您的困惑是您认为 n = 结构的维度，但实际上 n = 结构中的条目总数。所以使用嵌套循环是 O(n)

于 2013-03-15T00:41:08.183 回答