java - 数组和搜索算法:如何计算“搜索数组的平均N/2个步骤”的平均值？

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

在我看来，算法执行的“步骤”是
实际上是算法访问的数组的位置。因为
他们说插入数组是一步完成的，因为
只需将数据项插入第一个可用位置；
因此插入比搜索快。

但是实际上这是两种操作-一种是访问
数组位置，两个实际上是在其中插入数据项
内存位置。

我很好奇他们为什么不考虑实际情况
插入(如果是Search，则为比较操作)
操作(在我看来)。我从未见过任何人讨论
讨论算法时，有关该操作的内容很多。

与计算机内存有关的是仅访问
内存位置很麻烦，而且操作
实际上将数据项放在内存位置而不是
有多深思？它不会吞噬计算机的
资源？ (希望我已经清楚地说明了这个问题!)

其次，(假设数组没有重复项)我已经阅读了Search算法(我认为它与线性搜索有关)，平均需要N / 2步(step =数组位置的访问)搜索数组中是否有N个数据项。 我的问题是，该平均值如何计算。

注意:我刚刚开始阅读Robert Lafore的“Java中的数据结构和算法”书，而且我不确定应该确切地读什么书(计算机内存？数组项如何放置在内存中？混乱!)。对我来说很清楚。因此，也欢迎提供任何提示。

最佳答案

先前的答案似乎正确地解决了＃1或＃2的问题，但并非两者都对，因此最终我不得不编写自己的答案:

在谈论将项目添加到无序数组时，“插入”一词具有误导性。只说“追加”会更清楚。 OP表示“数据项只是简单地插入到第一个可用位置”，对于数组，第一个可用位置是最后一个项目之后的位置。 (理论上的数组是神话般的野兽，它们总是在末尾具有额外的可用空间。)因此，该项目将简单地附加在数组的末尾，而这仅仅是一次写入操作。 (如果插入点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次操作。