二元搜索(插入)的有序列表的复杂性 [英] Complexity for Binary Search (Insertion) for an ordered list

问题描述

我了解无法对无序数组执行二进制搜索.我也了解到，在有序数组中进行二进制搜索的复杂度为 O(log(n)).

I understand that binary search cannot be done for an unordered array. I also understand that the complexity of a binary search in an ordered array is O(log(n)).

我可以问

1. 有序数组?我从一本教科书上看到，它说是 O(n).为什么它不是 O(1)，因为它可以直接插入，就像线性搜索.

1. what is the complexity for binary search(insertion) for an ordered array? I saw from a textbook, it stated that the complexity is O(n). Why isn't it O(1) since, it can insert directly, just like linear search.

由于二进制搜索无法在无序列表中进行，所以为什么可能进行插入，复杂度为 O(N)?

Since binary search can't be done in unordered list, why is it possible to do insertion, with a complexity of O(N)?

推荐答案

插入列表的复杂度取决于所使用的数据结构:

insertion into list complexity depends on used data structure:

1. 线性阵列

在这种情况下，您需要将所有插入项从插入索引中移出一个项，以便为新插入的项腾出空间.这是复杂度 O(n).

In this case you need to move all the items from index of inserting by one item so you make room for new inserted item. This is complexity O(n).

链接列表

在这种情况下，您只是更改了上一个/下一个项目的指针，所以它是 O(1)

In this case you just changing the pointers of prev/next item so this is O(1)

现在，如果要使用二进制搜索(如您所注意到的)，则可以使用有序列表，但是只能使用数组.将项 a0 插入有序数组 a [n] 的bin搜索意味着:

Now for the ordered list if you want to use binary search (as you noticed) you can use only array. The bin-search insertion of item a0 into ordered array a[n] means this:

1. 查找放置 a0

1. find where to place a0

这是bin搜索的一部分，例如，找到索引 ix 这样:

This is the bin search part so for example find index ix such that:

a[ix-1]<=a0 AND a[ix]>a0 // for ascending order

这可以通过在 O(log(n))

插入项目

因此您需要首先将所有 i> = ix 项移动一个以放置，然后放置该项:

so you need first to move all the items i>=ix by one to make place and then place the item:

for (int i=n;i>ix;i--) a[i]=a[i-1]; a[ix]=a0; n++;

如您所见，这是 O(n).

放在一起

所以 O(n + log(n))= O(n)这就是为什么.

顺便说一句.可以对非严格排序的数据集进行搜索(尽管不再称为二进制搜索)，请参见

BTW. search on not strictly ordered dataset is possible (although it is not called binary search anymore) see

• 近似搜索的工作原理

这篇关于二元搜索(插入)的有序列表的复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！