1. 能够用二分法解决的题目的特点
（1）题目问题的典型问法：最大化在满足某条件下的解值或最小化该解值； （2）能够使用二分法的充分必要条件：问题的解具有单调满足性； （3）时间复杂度需要log(n)优化。2. 解的单调满足性
二分算法的单调满足性：
对于最小化问题，假设值x满足题目解要求的条件，那么对任意的y>x，y也都必然
满足该条件。而相反方法不一定都满足，也不一定都不满足，还可能存在更小的解，
此时就需要去更小的范围（一般令r=mid-1）里二分搜索最小解。最大化问题，则相反。
在这样的描述下，单调就是说：在大于或小于已知解的单一方向上（有且只有一个
方向）的所有值也都满足该解满足的题目条件。
3.log(n)到底能将时间复杂度降低到什么程度
给大家看几个参数：
（1）对于现代计算机的CPU，1秒内执行的基本指令(+-*/)条数大概是：10^8条。
题目中常常看到时间复杂度要求1s，也就是说你for循环体的执行次数要小于10^8次。
（2）几个数值：2^10=10^3,2^20=10^6,2^30=10^9,2^60=10^18（此处“=”为约等于）
1）对于规模为n=10^8的问题：
O(n)的解法可能超时；
O(log(n))解法可过：
O(log(n))=O(log(10^8))=O(60)接近常数级，从10^8降到不足10^2，多么大的跨越。
2）对于规模为n=10^5的问题：
O(n^2)解法超时；
O(nlog(n))解法可过：
log(10^5)<20,O(nlog(n))=O(n*20)=O(2*10^6)<O(10^7)，不会超时。
（3）所以可以根据问题规模n去推测可能的解法，排除掉超时的解法，选择有把握的。 说法错误之处还望指出。
全部评论
(0) 回帖