O(N)
O(logN)
O(N*N)
O(N*logN)
可得k=log2n,(是以2为底,n的对数)
第一次,在 个中找
第二次,在 个中找
第三次,在 个中找
. . .
第 k 次,在 个中找
故 ,
1. 顺序查找,时间复杂度为O(n)
2. 二分查找,时间复杂度为O(log2n)
3. 插值查找,关键字分布又比较均匀, 时间复杂度为O(log2(log2n))
4. 斐波那契查找,时间复杂度为O(log2n)
5. 树表查找
6. 分块查找,关键字构成一个索引表
7. 哈希查找,以空间换时间的算法
对于一个排序好的的数组进行查找,时间复杂度为 O(lgn)
这道题你会答吗?花几分钟告诉大家答案吧!
扫描二维码,关注牛客网
下载牛客APP,随时随地刷题