给定一个排序数组，确定它是否包含给定的数字 x：而不是使用二分查找，即将数组分成两部分。
如果我把数组分成三部分，递归查找这三部分中的元素。那么这个算法的时间复杂度或顺序（就数组的大小 n 而言）是多少？
问问题
357 次
1 回答
1
复杂性与二分查找相同。
最初的二分搜索包括两个阶段。首先在原始数组上执行恒定数量的步骤，然后对一半大小的数组进行递归调用。因此复杂度可以表示为
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
于 2013-09-29T07:19:41.813 回答