复杂度 - 输入长度
Complexity - input length
我目前正在学习复杂性（或效率，不管你怎么称呼它），我在我得到的一本书中读到了它。
写了一些我觉得很无意义的东西，我需要一个解释。我试过在线查找，但我没有找到他们给出的这个特定示例的答案。
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 ...
对我来说没有任何意义。
有人愿意解释一下吗？他们肯定不会在那里解释这个。
阅读评论说这本书是用希伯来语写的，我认为这个问题是翻译错误或校对中的其他错误。输入长度 "input length is the measurement that indicates the work load of an algorithm" 的注释中给出的定义与您认为该术语在英语中的含义完全不匹配。
为了回答有关复杂性的问题，他们在多个地方重复使用了变量 'n'，这让人有些困惑。他们用'n'来描述数组的维度，来描述复杂度。 O(n) 仅仅意味着复杂度与输入呈线性关系。 O(n^2) 将是指数复杂度。在这种情况下，对于 n*n 元素的数组，输入是 n*n 或 n^2，但算法的复杂度仍然是 O(n)（或线性）。这是因为该算法仍然只对每个输入元素进行一次操作，无论输入是 n 还是 n*n。如果它对每个元素进行 2 次或 3 次操作，它仍然是线性的，因为 3n 和 n 都是线性函数（任何 x*n 都是线性的）。
希望对您有所帮助。
这是一个常见的误解（在 SO 上很常见），即扫描具有 n*n 个元素的二维数组的复杂性是 O(n^2)。不是，是O(n)。扫描是一种线性操作，一个元素接一个元素。
二维数组是客套的虚构，它实际上只是为了方便访问一维数组。毕竟，在正确实现数组的语言中（即 none 这个指向内存块的指针数组），二维数组只是一组相邻的内存位置。即使在将二维数组实现为指针数组的语言中，它们也只是带有中断的线性内存段
如果对 2D 数组的扫描是 O(n^2) 那么您可以通过忽略 2d-ness 并只扫描底层的 1d 内存块来神奇地将其转换为 O(n)。
O(n^2) 描述了不同的操作复杂度 class，例如对输入中的每对元素进行操作的操作。
Big-O 表示法用于对算法类型（复杂性 类）进行分类，而不一定是 运行 实际需要多少时间。例如 O(cn) 就是 O(n)，其中 c 是常数。
n 是输入的大小，无论该输入是一个 nxn 矩阵还是只是一个 'n' 长度数组。 big-O 'n' 和程序变量名指的不是同一件事。
我目前正在学习复杂性（或效率，不管你怎么称呼它），我在我得到的一本书中读到了它。 写了一些我觉得很无意义的东西，我需要一个解释。我试过在线查找，但我没有找到他们给出的这个特定示例的答案。
For an algorithm that gets the max number in a single-dimensional array the size of
nthe input length would ben."For an algorithm that gets the max number in a two-dimensional array the size of
n*nthe input length would still ben."
我不明白为什么输入长度在这两种情况下都是“n”，即使对于二维你必须通过 n*n 数字......
它说
input length = the amount of work done ...
对我来说没有任何意义。 有人愿意解释一下吗？他们肯定不会在那里解释这个。
阅读评论说这本书是用希伯来语写的，我认为这个问题是翻译错误或校对中的其他错误。输入长度 "input length is the measurement that indicates the work load of an algorithm" 的注释中给出的定义与您认为该术语在英语中的含义完全不匹配。
为了回答有关复杂性的问题，他们在多个地方重复使用了变量 'n'，这让人有些困惑。他们用'n'来描述数组的维度，来描述复杂度。 O(n) 仅仅意味着复杂度与输入呈线性关系。 O(n^2) 将是指数复杂度。在这种情况下，对于 n*n 元素的数组，输入是 n*n 或 n^2，但算法的复杂度仍然是 O(n)（或线性）。这是因为该算法仍然只对每个输入元素进行一次操作，无论输入是 n 还是 n*n。如果它对每个元素进行 2 次或 3 次操作，它仍然是线性的，因为 3n 和 n 都是线性函数（任何 x*n 都是线性的）。
希望对您有所帮助。
这是一个常见的误解（在 SO 上很常见），即扫描具有 n*n 个元素的二维数组的复杂性是 O(n^2)。不是，是O(n)。扫描是一种线性操作，一个元素接一个元素。
二维数组是客套的虚构，它实际上只是为了方便访问一维数组。毕竟，在正确实现数组的语言中（即 none 这个指向内存块的指针数组），二维数组只是一组相邻的内存位置。即使在将二维数组实现为指针数组的语言中，它们也只是带有中断的线性内存段
如果对 2D 数组的扫描是 O(n^2) 那么您可以通过忽略 2d-ness 并只扫描底层的 1d 内存块来神奇地将其转换为 O(n)。
O(n^2) 描述了不同的操作复杂度 class，例如对输入中的每对元素进行操作的操作。
Big-O 表示法用于对算法类型（复杂性 类）进行分类，而不一定是 运行 实际需要多少时间。例如 O(cn) 就是 O(n)，其中 c 是常数。
n 是输入的大小，无论该输入是一个 nxn 矩阵还是只是一个 'n' 长度数组。 big-O 'n' 和程序变量名指的不是同一件事。