我刚刚开始学习Java中的数据结构和算法（从数组开始）。我有两个问题。
-
在我看来，算法执行中的"步骤"是实际上是算法访问的数组的位置。因为他们说阵列中的插入只需一步，因为数据项被简单地插入到第一可用位置；因此插入比搜索更快。
但实际上这是两种操作——一种是访问数组位置，二实际上是将数据项插入内存位置。
我很好奇他们为什么不多考虑实际情况插入（或搜索时的比较操作）操作（在我看来）。我从未见过有人讨论当讨论算法时，关于该操作的很多内容
只访问内存位置很麻烦实际上把数据项放在内存位置不是什么考虑了很多？它不是吃掉了电脑的吗资源？（我希望我已经把这个问题说清楚了！）
-
其次，（假设数组没有重复项）我读到在搜索算法中（我认为这是关于线性搜索），如果数组中有N个数据项，则搜索数组平均需要N/2个步骤（步骤=访问数组位置）我的问题是这个平均值是如何计算的
注意：我刚刚开始阅读Robert Lafore的《Java中的数据结构和算法》一书，我不确定我到底应该读什么（计算机内存？，数组项是如何放置在内存中的？混淆！）来让我明白这些事情。因此，也欢迎任何关于这方面的提示
以前的答案似乎要么是#1，要么是#2，但不是两者都对，所以最终我不得不写自己的：
-
当谈到向无序数组中添加项时，术语"插入"会产生误导。仅仅说"附加"会更清楚。OP表示"数据项只是插入到第一个可用的位置"，在数组的情况下，第一个可用位置是最后一个项之后的位置。（理论数组是神话中的野兽，在数组末尾总是有额外的可用空间。）因此，项目将简单地附加在数组末尾，这只是一次写入操作。（如果插入点
i位于阵列的中间，则所有后续项都必须向上移动一个位置以为其腾出空间，这将是(N-i)读取和另一个(N-i)写入，除了用于将项存储在i的一个写入之外。） -
对于搜索项目，查找单个搜索的平均操作次数等于将所有可能搜索的操作次数相加并除以搜索次数。搜索位置1的项目需要一次运算，搜索位置2的项目需要两次运算，而搜索位置N的项目需要N次运算，因此公式为1+2+3+…+N、 已知其等于N*（N+1）/2。除以N得到（N+1）/2，相当于N/2，因为在这些类型的计算中，我们忽略了常数因子。（"+1"是一个常数。）注意：所有这些不仅假设没有重复项，而且假设每个被搜索的项最终都在数组中找到，因为搜索不在数组中的项将导致完整的数组遍历，这将需要N次操作。
第二个问题首先：其实很简单，如果你有一个有100个位置的数组，并搜索一个随机位置的东西，它在每个数组槽中的几率为1/100。此外，访问阵列的1-100个位置以找到您想要的东西的机会是相等的。
最好的情况是1（你在第一个插槽中找到它），最坏的情况是100（在最后一个插槽中），平均值介于这两者之间（分布均匀），所以是50。（有一个相同的变化，即必须访问一半以上的阵列插槽，而访问不到一半的阵列插槽。）
翻译成可变数字，你会得到：
最佳情况：1
最坏情况：N
平均值：N/2
第一个问题：
学习一些C可能会让这一点变得更清楚。因为，数组只不过是经过处理的内存块。假设你有一个int的数组，然后每个CCD_ 6占用一块存储器（例如16位/2字节）。当你有一个100个int的数组时，你有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
ans到q1：假设您在数组中保持一组项未排序，并且您知道数组的长度，那么要附加一个项，您所要做的就是将新项分配给紧跟在最后一个元素之后的数组元素。这需要一次手术。如果数据保存在其他数据结构中，插入项目的成本可能会更高，但搜索速度会更快。所以，这总是一种权衡。
问题2的答案：假设一个数组中有n个元素，并且以相同的概率搜索各种元素。您将在一个步骤中找到元素1，在两个步骤中发现元素2。。。元素n在n个步骤中。如果求和1+2+3…+n除以n，得到n（n+1）/2/n=（n+1/2）同样，如果您决定保留一个已排序的数组而不是未排序的数组，那么您可以进行二进制搜索，并在log2（n）中找到一个项目
在数组或其他数据类型中搜索数据的搜索时间在很大程度上取决于您使用的搜索算法。一些算法可能具有良好的时间复杂度，但空间复杂度较差，反之亦然。分治算法使用时间复杂度Log2（N）进行搜索。在计算诸如（N/2）之类的运行时间时，总是需要对算法有很好的理解。此外，时间复杂性有两种情况，可以有最坏的情况和最好的情况。N/2必须属于这两个时间复杂度实例中的一个