<分区>
给定一个排序数组，确定它是否包含给定的数字 x:
而不是使用二进制搜索，即将数组分成两部分。
如果我把数组分成三部分，递归的在这三部分中找元素。那么这个算法的时间复杂度或阶数(根据数组的大小 n)是多少
<分区>
给定一个排序数组，确定它是否包含给定的数字 x:
而不是使用二进制搜索，即将数组分成两部分。
如果我把数组分成三部分，递归的在这三部分中找元素。那么这个算法的时间复杂度或阶数(根据数组的大小 n)是多少
最佳答案
复杂度将与二分查找相同。
最初的二分查找由两个阶段组成。首先在原始数组上进行恒定数量的步骤，然后对一半大小的数组进行递归调用。因此复杂度可以表示为
T(n) = C1 + T(n/2)
如果你分成三部分，你进行了更多的比较和条件测试，但仍然对大小为n的数组进行恒定时间操作，然后你递归调用大小为n/3的数组。这意味着
T(n) = C2 + T(N/3)
两个函数的计算结果都是 Theta(log n)。
你可以概括。如果我分成 k 部分会怎么样。复杂度为
f(n) = Ck + f(n/k)
结果是
f(n) = Ck log(n)/log(k) + Dk
随着 k 的增加，您将获得更大的对数除数，但常数 Ck 和 Dk 也会增加，因为您在跳入子数组之前执行了更多操作。考虑一下 n=k
关于algorithm - 下面算法的时间复杂度是多少，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/19075326/