算法基础:
一、大O表示法:
指示算法的速度有多快，用于指出随数量的增大，算法的所需步骤增加的速度，常见的大O运行时间(时间复杂度)：O(1)表示常数阶时间复杂度O(log n)，也叫对数时间复杂度，这样的算法包括二分查找。O(n)，也叫线性阶时间复杂度，这样的算法包括简单查找。O(n * log n), （n*对数复杂度）O(n^2)，平方阶时间复杂度O(n!)，阶乘阶时间复杂度复制代码
n越来越大时，算法效率图解：
要点
-
1.二分查找法只适用于从有序的队列中进行查找(比如数字和字母等)，将队列排序后再进行查找
-
2.二分查找法的运行时间为对数时间O(㏒₂n) ，即查找到需要的目标位置最多只需要㏒₂n步，假设从[0,99]的队列(100个数，即n=100)中寻到目标数30，则需要查找步数为㏒₂100 , 即最多需要查找7次( 2^6 < 100 < 2^7)
-
3.简单查询(遍历查询)的运行时间为线性时间O(n), 假设从[0,99]的队列中(n=100)寻到目标数30，则最多需要查找步数为100步
-
4.对于容器内数量很少的情况下，2种查找也许没啥差别，当数量大的情况下，差别就很大，比如假设查找比较步骤一次需要1秒，当容量数目为100000时，O(n)需要100000秒即约27.8小时，而logn只需要 2^16 < 100000 < 2^17，即17秒，这差距非常的大
-
5.时间复杂度都是针对最坏的情况所表示的，表示最多需要多少步
案例
从1~99的容器内，找出指定的数字；
java实现:A：简单查找法，即遍历查找，全部遍历直到找到指定的数便停止/** * 简单查找 * @param array 传入存放全部数据的容器 * @param target 需要查找的目标数 * @return */public Integer search(Integer[] array,int target){ for(int i=0;i target){ //如果中间值大于目标数，则将highr点位置移动mid位置左边 hight = mid-1; } if(array[mid] < target){ //如果中间值小于目标数，则将low点位置移动mid位置右边 low = mid+1; } } return null;}复制代码 图解:
假设容器中为[1,99]，共99个数 必须明白因为时间复杂度是针对最坏情况的，二分查找所需最多为7步，简单遍历法最多为99步(当查找的是数99);
根据实际需要查找的数，所消耗的步骤不一定一样，但都不会超过时间复杂度
步骤图解如下所示([1，99]，即n=99，查找的数为30):
时间复杂度推算过程:
参考:https://blog.csdn.net/frances_han/article/details/6458067 二分查找的基本思想是将n个元素分成大致相等的两部分，去a[n/2]与x做比较，如果x=a[n/2],则找到x,算法中止；如果x<a[n/2],则只要在数组a的左半部分继续搜索x,如果x>a[n/2],则只要在数组a的右半部搜索x. 时间复杂度无非就是while循环的次数！ 总共有n个元素， 渐渐跟下去就是n,n/2,n/4,....n/2^k，其中k就是循环的次数 由于你n/2^k取整后>=1 即令n/2^k=1 可得k=log2n,（是以2为底，n的对数） 所以时间复杂度可以表示O()=O(logn)
有兴趣共同进步可以扫描关注微信订阅号