java - 数组和搜索算法 : How is the "average N/2 steps to search an array" average value calculated?

Question

我刚刚开始学习 Java 中的数据结构和算法(从数组开始)。我有两个问题。

1. 在我看来，算法执行中的“步骤”是实际上是算法访问的数组的位置。因为他们说数组中的插入一步发生，因为数据项被简单地插入到第一个可用位置；因此插入比搜索快。

   但实际上是两种操作——一种是访问array position(s)，两个实际上是在那个里面插入数据项内存位置。

   我很好奇他们为什么不多考虑一下实际情况插入(或搜索情况下的比较操作)操作(在我看来)。没见过有人讨论在讨论算法时，很多关于该操作的内容。

   是不是关于计算机内存的东西，只访问一个内存位置是一件令人烦恼的事情，并且操作实际上将数据项放在内存位置不是什么考虑了多少？不会吃掉电脑吗资源？ (希望我已经把这个问题说清楚了!)

2. 其次，(假设数组没有重复项)我在搜索算法中读到过(我认为它是关于线性搜索的)，它需要平均 N/如果数组中有 N 个数据项，则分 2 步(step=访问数组位置)搜索数组。 我的问题是这个平均值是如何计算的。

注意:我刚刚开始阅读 Robert Lafore 的“Java 中的数据结构和算法”一书，但我不确定到底应该阅读什么内容(计算机内存？数组项如何放置在内存中？困惑!)让我清楚这些事情。因此，我们也欢迎任何相关提示。

Answer 1

以前的答案似乎对#1 或#2，但不是两个都对，所以最终我不得不自己写:

1. 在谈论将项目添加到无序数组时，术语“插入”具有误导性。只说“附加”会更清楚。 OP 说“数据项只是插入到第一个可用位置”，在数组的情况下，第一个可用位置是最后一项之后的位置。 (理论上的数组是神话般的野兽，最后总是有额外的可用空间。)因此，该项目将简单地附加在数组的末尾，这只是一个写操作。 (如果插入点 i 是在数组的中间，那么所有后续项都必须向上移动一个位置为其腾出空间，这就是 (N-i) 读取和另一个 (N-i) 写入，除了用于将项目存储在 i 的一次写入之外。)

2. 对于搜索一个项目，计算单次搜索的平均操作次数等于将所有可能搜索的操作次数相加并除以搜索次数。查找位置 1 的项目需要一次操作，查找位置 2 的项目需要两次操作，查找位置 N 的项目需要 N 次操作，所以公式为 1 + 2 + 3 + ... + N，其中 is known to be等于 N*(N+1)/2。除以 N 得到 (N+1)/2，相当于 N/2，因为在这些类型的计算中我们忽略了常数因子。 ('+1' 是一个常数因子。)注意:所有这些假设不仅没有重复项，而且还假设每个寻找的项目最终都在数组中找到，因为搜索的项目不是在数组中将导致完整的数组遍历，这将需要 N 次操作。