我知道无法对无序数组进行二分查找。
我还了解到,在有序数组中进行二分查找的复杂度为 O(log(n))
。
可以问一下吗
二分查找(插入)的复杂度是多少? 有序数组?我从教科书上看到,它说复杂性 是
O(n)
。为什么不是O(1)
因为它可以直接插入,就像 线性搜索。既然无序列表不能进行二分查找,那又是为什么呢 可以插入,复杂度为
O(N)
?
最佳答案
插入列表的复杂性取决于使用的数据结构:
线性阵列
在这种情况下,您需要将所有项目从插入索引中移动一个项目,以便为新插入的项目腾出空间。这是复杂度
O(n)
。链表
在这种情况下,您只需更改上一个/下一个项目的指针,所以这是
O(1)
现在对于有序列表,如果你想使用二进制搜索(正如你注意到的那样),你只能使用数组。项目 a0
到有序数组 a[n]
的 bin-search 插入意味着:
找到放置
的位置a0
这是 bin 搜索部分,例如找到索引
ix
这样:a[ix-1]<=a0 AND a[ix]>a0 // for ascending order
这可以通过
O(log(n))
中的 bin search 来完成
插入项目
所以你需要先将所有的项目
i>=ix
移动一个位置,然后放置项目:for (int i=n;i>ix;i--) a[i]=a[i-1]; a[ix]=a0; n++;
如您所见,这是
O(n)
。放在一起
所以
O(n+log(n)) = O(n)
这就是原因。
顺便说一句。可以搜索非严格排序的数据集(虽然它不再称为二进制搜索)参见
关于arrays - 有序列表的二进制搜索(插入)的复杂性,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/36526064/