三分查找和二分查找时间复杂度

三分查找和二分查找的时间复杂度分别是多少呢？

三分查找的时间复杂度为O(2log3(n))，其中n是集合的大小。三分查找是一种在凸性函数中寻找极值的方法，它将集合分为三个部分，然后判断解在哪个部分中，并调整集合的上下界，重复这个过程直到找到目标元素。由于每次将集合分为三个部分，所以每层需要比较的次数为2，而递归树的高度为log3(n)，因此时间复杂度为O(2log3(n))。

二分查找的时间复杂度为O(logn)，其中n是集合的大小。二分查找是一种在单调有序集合中查找元素的方法，它将集合分为两个部分，然后判断解在哪个部分中，并调整集合的上下界，重复这个过程直到找到目标元素。由于每次将集合分为两个部分，所以每层需要比较的次数为1，而递归树的高度为logn，因此时间复杂度为O(logn)。

相关问题

常用算法的时间复杂度

常用算法的时间复杂度可以总结如下：

1. 常数时间复杂度：O(1)
无论输入规模多大，算法的执行时间都是固定的。

2. 对数时间复杂度：O(log n)
例如二分查找算法，每次都将问题规模减半。

3. 线性时间复杂度：O(n)
例如遍历数组、查找最大值等，执行时间与输入规模成正比。

4. 线性对数时间复杂度：O(n log n)
例如快速排序、归并排序等，通常基于分治思想。

5. 平方时间复杂度：O(n^2)
例如冒泡排序、选择排序等，通常嵌套循环导致的。

6. 立方时间复杂度：O(n^3)
例如三重嵌套循环导致的算法。

7. 指数时间复杂度：O(2^n)
例如求解子集、背包问题等，通常基于穷举所有可能性。

以上只是常见的一些时间复杂度，实际应用中还有其他更高阶的复杂度。需要根据具体情况选择合适的算法以及考虑算法的时间复杂度。