作业帮O(n) 和O(log2n)是什么意思?
来源：学生作业帮 编辑：作业帮 分类：数学作业 时间：2024/07/15 09:22:27
O(n) 和O(log2n)是什么意思?
在长度为n的有序线性表中进行二分查找,最坏情况下的比较次数应该 是n 可是为什么书上的答案是 O(log2n)?
在长度为n的有序线性表中进行二分查找,最坏情况下的比较次数应该 是n 可是为什么书上的答案是 O(log2n)?
是有序线性表,二分查找,不可能比较n次啊,比较n次你等于是把整个线性表遍历了一遍.二分查找每次可以排除一半元素.
比如123456789,你要找2,首先查中间元素5,大于2,所以直接排除掉5右边的6789
然后在1234里继续二分查找.
每次排除1/2的元素,所以是O(log2n)
再问： 哦哦 这样啊 那 O（n)是什么意思啊
再答： n是元素的个数 O（n)意味着你把每个元素都访问一遍，这样你当然可以找到要查找的数了。但是对于有序数组，没必要这样遍历整个数组。
比如123456789,你要找2,首先查中间元素5,大于2,所以直接排除掉5右边的6789
然后在1234里继续二分查找.
每次排除1/2的元素,所以是O(log2n)
再问： 哦哦 这样啊 那 O（n)是什么意思啊
再答： n是元素的个数 O（n)意味着你把每个元素都访问一遍，这样你当然可以找到要查找的数了。但是对于有序数组，没必要这样遍历整个数组。