二分法时间复杂度

编程入门行业动态更新时间:2024-10-07 09:25:13

二分法时间<a href=https://www.elefans.com/category/jswz/34/1767520.html style= 复杂度"/>

二分法时间复杂度

二分法相当于不断等分分割一组数组，并在分割得到的两个子数组中，找到一个符合条件的数组继续分割，一次循环知道子数组的元素个数为1.
可见，二分法的查找过程相当于在一颗二叉树中寻找一条从root节点到叶节点的路径，二叉树的每一层是所有可能的分割子数组，其中root节点的数值是最开始的数组数量总数N，其他节点的是其父节点的数组数值的二分之一，所有叶节点的数值是1。
因此，可以知道，二叉树的层数就是二分法的调用次数，调用次数就是二分法的时间复杂度，有：
N/(2ⁿ) = 1;
-> N = 2ⁿ;
-> n = log₂N;
所以，时间复杂度是logN.

更多推荐

二分法时间复杂度

本文发布于:2024-02-27 21:16:37，感谢您对本站的认可！

本文链接:https://www.elefans.com/category/jswz/34/1766699.html