algorithm - 复杂度 - 输入长度

Question

我目前正在学习复杂性(或效率，不管你怎么调用它)，我在我得到的一本书中读到了它。写了一些我觉得很无意义的东西，我需要一个解释。我试过在线查找，但我没有找到他们给出的这个特定示例的答案。

For an algorithm that gets the max number in a single-dimensional array the size of n the input length would be n.

"For an algorithm that gets the max number in a two-dimensional array the size of n*n the input length would still be n."

我不明白为什么输入长度在这两种情况下都是“n”，即使对于二维你必须通过 n*n 数字...它说

input length = the amount of work done ...

对我来说没有任何意义。有人愿意解释一下吗？他们肯定不会在那里解释。

Answer 1

这是一个常见的误解(在 SO 上很常见)，即扫描具有 n*n 元素的二维数组的复杂度是 O(n^2) .不是，它是 O(n)。扫描是一种线性操作，一个元素接一个元素。

二维数组是一种礼貌的虚构，它实际上只是访问一维数组的一种便利。毕竟，在正确实现数组的语言中(即没有指向内存块的指针数组)，二维数组只是一组相邻的内存位置。即使在将二维数组实现为指针数组的语言中，它们也只是带有中断的线性内存段

如果二维数组的扫描是 O(n^2) 那么您可以通过忽略二维性而神奇地将它转换为 O(n)扫描底层的 1d 内存块。

O(n^2) 描述了不同复杂度的操作类别，例如对输入中的每对元素进行操作的操作。