二分法算法时间复杂度分析,该怎么处理
二分法算法时间复杂度分析
数据结构与算法分析:C语言描述
对分法算法分析:
Clearly all the work done inside the loop is O(1) per iteration, so the analysis requires determining the
number of times around the loop. The loop starts with high - low = n - 1 and finishes with high - low -1.
Every time through the loop the value high - low must be at least halved from its previous value; thus, the
number of times around the loop is at most log(n - 1) + 2. (As an example, if high - low = 128, then the
maximum values of high - low after each iteration are 64, 32, 16, 8, 4, 2, 1, 0, -1.) Thus, the running
time is O(log n). Equivalently, we could write a recursive formula for the running time, but this kind of
brute-force approach is usually unnecessary when you understand what is really going on and why.
问题: log(n - 1) + 2这里为什么要+2 ?
当然能理解最后是O(log n),就是没有明白作者的完整分析思路,请知道同学，解答一下非常感谢!
------解决方案--------------------
注意这里是算法分析，不是实际计算
算法分析，考虑的情况比实际计算（执行）复杂，不可能完全精确计数。
你这里一个具体的数据，把问题简单化，片面化了，所以不具有代表性。
如果这得需要精确检测，你需要所有合乎要求的数据都拿来测试，一一检测
此外，注意算法分析，不是精确计数。。它分析的是数量级。
一般来说,算法分析的结果多半是这样的：
T(N) =O(f(N))
基本上是以下几种数据中的一个，有时候也会用O(n^(1/3)),O(n^(4/3)) 这样的 表示。
O(1)<O(log(n))<O(log*(n))<n<O (nlog(n))<O(n^2)<O(n^k) ; k>2
数据结构与算法分析:C语言描述
对分法算法分析:
Clearly all the work done inside the loop is O(1) per iteration, so the analysis requires determining the
number of times around the loop. The loop starts with high - low = n - 1 and finishes with high - low -1.
Every time through the loop the value high - low must be at least halved from its previous value; thus, the
number of times around the loop is at most log(n - 1) + 2. (As an example, if high - low = 128, then the
maximum values of high - low after each iteration are 64, 32, 16, 8, 4, 2, 1, 0, -1.) Thus, the running
time is O(log n). Equivalently, we could write a recursive formula for the running time, but this kind of
brute-force approach is usually unnecessary when you understand what is really going on and why.
int binarySear(int[] A, int X, int N){
int Left, Mid, Right;
Left = Mid = 0;
Right = N-1;
while (Left <= Right) {
Mid = (Left + Right)/2;
if(A[Mid] < X)
Left = Mid + 1;
else if (A[Mid] > X)
Right = Mid - 1;
else
return A[Mid];
}
return -1;
}
问题: log(n - 1) + 2这里为什么要+2 ?
当然能理解最后是O(log n),就是没有明白作者的完整分析思路,请知道同学，解答一下非常感谢!
------解决方案--------------------
注意这里是算法分析，不是实际计算
算法分析，考虑的情况比实际计算（执行）复杂，不可能完全精确计数。
你这里一个具体的数据，把问题简单化，片面化了，所以不具有代表性。
如果这得需要精确检测，你需要所有合乎要求的数据都拿来测试，一一检测
此外，注意算法分析，不是精确计数。。它分析的是数量级。
一般来说,算法分析的结果多半是这样的：
T(N) =O(f(N))
基本上是以下几种数据中的一个，有时候也会用O(n^(1/3)),O(n^(4/3)) 这样的 表示。
O(1)<O(log(n))<O(log*(n))<n<O (nlog(n))<O(n^2)<O(n^k) ; k>2