数组和搜索算法："average N/2 steps to search an array" 平均值是如何计算的？
Arrays and Search Algorithms: How is the "average N/2 steps to search an array" average value calculated?
我刚刚开始学习 Java 中的数据结构和算法（从数组开始）。我有两个问题。
在我看来，算法执行中的 "steps" 是
实际上是算法访问的数组的位置。因为
他们说数组中的插入一步发生，因为
数据项被简单地插入到第一个可用位置；
因此插入比搜索快。
但实际上是两种操作——一种是访问
array position(s)，两个实际上是在那个里面插入数据项
内存位置。
我很好奇他们为什么不多考虑一下实际情况
插入（或搜索情况下的比较操作）
操作（在我看来）。没见过有人讨论
在讨论算法时会详细介绍该操作。
是不是电脑内存的问题，只访问一个
内存位置是一件令人烦恼的事情，并且操作
实际上将数据项放在内存位置不是什么
考虑了多少？不会吃掉电脑吗
资源？ （希望我把这个问题说清楚了！）
其次，（假设数组没有重复项）我在搜索算法中读到过（我认为它是关于线性搜索的），平均需要 N/2步（step=访问一个数组位置）如果数组中有N个数据项，则搜索数组。 我的问题是这个平均值是如何计算的。
注意：我刚刚开始阅读 Robert Lafore 的 "Data Structures and Algorithms in Java" 书，我不确定我到底应该阅读什么（计算机内存？，数组项如何放置在内存中? 混淆！）让我清楚这些事情。所以也欢迎任何提示。
对问题 1 的回答：
假设您在一个数组中保持未排序的项目集，并且您知道数组的长度，那么要追加一个项目，您只需将新项目分配给紧跟在最后一个元素之后的数组元素。这需要一个单一的操作。如果数据保存在其他数据结构中，插入一个项目的成本可能更高，但搜索速度会更快。所以，这总是一个权衡。
对问题 2 的回答：
假设您在一个数组中有 n 个元素，并且您以相同的概率搜索各种元素。您将在一步中找到元素 1，在 2 步中找到元素 2...在 n 步中找到元素 n。如果对 1 + 2 + 3 ...+ n 求和并除以 n，则得到 n (n+1) /2/ n =( n+1)/2
同样，如果您决定保留排序数组而不是未排序数组，那么您可以进行二进制搜索并在 log2(n)
中找到一个项目
先问第二个问题：其实很简单，如果你有一个有 100 个位置的数组，并搜索一个随机位置的东西，它有 1/100 的机会在每个数组槽中。此外，访问数组的 1-100 个位置以找到所需内容的机会均等。
最好的情况是 1（你在第一个槽中找到它），最坏的情况是 100（它在最后一个槽中），平均值介于这两者之间（均匀分布），所以 50。（必须访问超过一半的数组槽和少于一半的数组槽是相同的变化。）
转换为可变数字，您将得到：
最佳情况：1
最坏情况：N
平均：N/2
第一个问题：
学习一些 C 可能会使这一点更清楚。因为，数组只不过是寻址的内存块。假设你有一个 int 的数组，那么每个
int占用一块内存（比如16-bit/2字节）。当你有一个 100 ints 的数组时，你有 100 个 16 位内存块一个接一个，所以直接访问其中一个你需要知道第一个块的位置，然后添加 16 位* 位置找到正确的内存块。对数组的引用无非是对第一个元素的内存块的引用，所以为了找到第42位的int，需要访问地址为adress of the first block的内存块 + 42 * length of each block.
相反，一个链表，其中每个元素都包含对下一个元素的引用（并且它们在内存中甚至不一定彼此靠近）将需要比常量时间更多的时间来找到位置 X 中的元素，因为您必须通过位置 X 之前的所有元素才能到达它。
数组通常是一种随机访问结构，这意味着您可以访问第 i 个元素，而不必先遍历前 i-1 个元素。因此，读取和写入数组的索引（映射到某个内存地址）都可以假定花费恒定的时间。
线性搜索要求您遍历数组的所有元素，直到找到您要查找的元素。平均 运行 时间是概率问题。第 i 个元素是您要查找的元素的概率是 1/n，您将必须遍历 i 个元素才能找到它。因此，预期的 运行 时间为：
1/n * (1 + 2 + ... + n) = 1/n * (n+1)*n/2 = (n+1)/2
在数组或其他数据类型中搜索数据的搜索时间在很大程度上取决于您使用的搜索算法。一些算法可能具有良好的时间复杂度但 space 复杂度较差，反之亦然。分而治之算法在时间复杂度上使用Log2(N)进行搜索。在计算运行时如(N/2)，总是需要对算法有很好的理解。另外，时间复杂度上有两种情况，可以有最坏情况和最好情况。 N/2 必须属于这两个时间复杂度实例之一
以前的答案似乎对#1 或#2，但不是两个都对，所以最终我不得不自己写：
术语 "inserting" 在谈论将项目添加到无序数组时具有误导性。只说 "appending" 会更清楚。 OP 说 "the data item is simply inserted at the first available position"，在数组的情况下，第一个可用位置是最后一项之后的位置。 （理论上的数组是神话般的野兽，最后总是有额外的空闲 space 可用。）所以，该项目将简单地附加在数组的末尾，这只是一个写操作。 （如果插入点 i 是在数组的中间，那么所有后续项都必须向上移动一个位置为其腾出空间，这就是 (N-i) 读取和另一个 (N-i) 写入，除了用于将项目存储在 i 的写入之外。）
对于一个项目的搜索，求出单次搜索的平均操作次数等于将所有可能搜索的操作次数相加除以搜索次数。查找位置 1 的项目需要一次操作，查找位置 2 的项目需要两次操作，查找位置 N 的项目需要 N 次操作，所以公式为 1 + 2 + 3 + ... + N，其中 is known to be 等于 N*(N+1)/2。除以 N 得到 (N+1)/2，相当于 N/2，因为在这些类型的计算中我们忽略了常数因子。 （'+1' 是一个常数。）注意：所有这些假设不仅没有重复，而且每个寻找的项目最终都在数组中找到，因为搜索的项目不是在数组中将导致完整的数组遍历，这将需要 N 次操作。
我刚刚开始学习 Java 中的数据结构和算法（从数组开始）。我有两个问题。
在我看来，算法执行中的 "steps" 是 实际上是算法访问的数组的位置。因为 他们说数组中的插入一步发生，因为 数据项被简单地插入到第一个可用位置； 因此插入比搜索快。
但实际上是两种操作——一种是访问 array position(s)，两个实际上是在那个里面插入数据项 内存位置。
我很好奇他们为什么不多考虑一下实际情况 插入（或搜索情况下的比较操作） 操作（在我看来）。没见过有人讨论 在讨论算法时会详细介绍该操作。
是不是电脑内存的问题，只访问一个 内存位置是一件令人烦恼的事情，并且操作 实际上将数据项放在内存位置不是什么 考虑了多少？不会吃掉电脑吗 资源？ （希望我把这个问题说清楚了！）
其次，（假设数组没有重复项）我在搜索算法中读到过（我认为它是关于线性搜索的），平均需要 N/2步（step=访问一个数组位置）如果数组中有N个数据项，则搜索数组。 我的问题是这个平均值是如何计算的。
注意：我刚刚开始阅读 Robert Lafore 的 "Data Structures and Algorithms in Java" 书，我不确定我到底应该阅读什么（计算机内存？，数组项如何放置在内存中? 混淆！）让我清楚这些事情。所以也欢迎任何提示。
对问题 1 的回答： 假设您在一个数组中保持未排序的项目集，并且您知道数组的长度，那么要追加一个项目，您只需将新项目分配给紧跟在最后一个元素之后的数组元素。这需要一个单一的操作。如果数据保存在其他数据结构中，插入一个项目的成本可能更高，但搜索速度会更快。所以，这总是一个权衡。
对问题 2 的回答： 假设您在一个数组中有 n 个元素，并且您以相同的概率搜索各种元素。您将在一步中找到元素 1，在 2 步中找到元素 2...在 n 步中找到元素 n。如果对 1 + 2 + 3 ...+ n 求和并除以 n，则得到 n (n+1) /2/ n =( n+1)/2 同样，如果您决定保留排序数组而不是未排序数组，那么您可以进行二进制搜索并在 log2(n)
中找到一个项目先问第二个问题：其实很简单，如果你有一个有 100 个位置的数组，并搜索一个随机位置的东西，它有 1/100 的机会在每个数组槽中。此外，访问数组的 1-100 个位置以找到所需内容的机会均等。
最好的情况是 1（你在第一个槽中找到它），最坏的情况是 100（它在最后一个槽中），平均值介于这两者之间（均匀分布），所以 50。（必须访问超过一半的数组槽和少于一半的数组槽是相同的变化。）
转换为可变数字，您将得到：
最佳情况：1
最坏情况：N
平均：N/2
第一个问题：
学习一些 C 可能会使这一点更清楚。因为，数组只不过是寻址的内存块。假设你有一个 int 的数组，那么每个
int占用一块内存（比如16-bit/2字节）。当你有一个 100 ints 的数组时，你有 100 个 16 位内存块一个接一个，所以直接访问其中一个你需要知道第一个块的位置，然后添加 16 位* 位置找到正确的内存块。对数组的引用无非是对第一个元素的内存块的引用，所以为了找到第42位的int，需要访问地址为adress of the first block的内存块 + 42 * length of each block.
相反，一个链表，其中每个元素都包含对下一个元素的引用（并且它们在内存中甚至不一定彼此靠近）将需要比常量时间更多的时间来找到位置 X 中的元素，因为您必须通过位置 X 之前的所有元素才能到达它。
数组通常是一种随机访问结构，这意味着您可以访问第 i 个元素，而不必先遍历前 i-1 个元素。因此，读取和写入数组的索引（映射到某个内存地址）都可以假定花费恒定的时间。
线性搜索要求您遍历数组的所有元素，直到找到您要查找的元素。平均 运行 时间是概率问题。第 i 个元素是您要查找的元素的概率是 1/n，您将必须遍历 i 个元素才能找到它。因此，预期的 运行 时间为：
1/n * (1 + 2 + ... + n) = 1/n * (n+1)*n/2 = (n+1)/2
在数组或其他数据类型中搜索数据的搜索时间在很大程度上取决于您使用的搜索算法。一些算法可能具有良好的时间复杂度但 space 复杂度较差，反之亦然。分而治之算法在时间复杂度上使用Log2(N)进行搜索。在计算运行时如(N/2)，总是需要对算法有很好的理解。另外，时间复杂度上有两种情况，可以有最坏情况和最好情况。 N/2 必须属于这两个时间复杂度实例之一
以前的答案似乎对#1 或#2，但不是两个都对，所以最终我不得不自己写：
术语 "inserting" 在谈论将项目添加到无序数组时具有误导性。只说 "appending" 会更清楚。 OP 说 "the data item is simply inserted at the first available position"，在数组的情况下，第一个可用位置是最后一项之后的位置。 （理论上的数组是神话般的野兽，最后总是有额外的空闲 space 可用。）所以，该项目将简单地附加在数组的末尾，这只是一个写操作。 （如果插入点
i是在数组的中间，那么所有后续项都必须向上移动一个位置为其腾出空间，这就是(N-i)读取和另一个(N-i)写入，除了用于将项目存储在i的写入之外。）对于一个项目的搜索，求出单次搜索的平均操作次数等于将所有可能搜索的操作次数相加除以搜索次数。查找位置 1 的项目需要一次操作，查找位置 2 的项目需要两次操作，查找位置 N 的项目需要 N 次操作，所以公式为 1 + 2 + 3 + ... + N，其中 is known to be 等于 N*(N+1)/2。除以 N 得到 (N+1)/2，相当于 N/2，因为在这些类型的计算中我们忽略了常数因子。 （'+1' 是一个常数。）注意：所有这些假设不仅没有重复，而且每个寻找的项目最终都在数组中找到，因为搜索的项目不是在数组中将导致完整的数组遍历，这将需要 N 次操作。