关于数据查找算法之一二分法的浅谈
算法是一组完成任务的指令。任何代码片段都可以被称之为算法，为了提高查找的速度，就浅显的谈论一下二分法。
假设我们要在牛津大辞典中查找一个O开头的字母，可以从头开始翻页，但是这很慢，我们肯定从中间开始翻页，因为我们知道O从中间开始。这样就可以很快的将其找出来。
这是一个查找问题，像这种查找问题我们都可以使用二分法来解决问题。
二分查找是一种算法，其输入是一个有序的元素列表。如果要查找的元素包含在列表中，二分查找返回其位置；否则返回null。
在介绍二分法的时候，我们先谈一下简单查找，俗称傻找。举个例子，如果我要从（1-100）100个数中找到一个数，简单查找就会从一开始，查找，如果这个数是100，就查找100次。而二分法就会从50开始，大了到25，再到14->7->3->2->1，总共查找7次，就是〖log2〗^n
这可能还不是很明显，但是如果有40亿个数据的话，使用简单查找，需要40亿毫秒，40亿ms等于46天。而我们使用二分法来说，只需要进行指数计算，进行32次运算，就是32ms！！
其实对于计算速度，我们可以用大O来表示，大O表示法是一种特殊的表示方法，他指出了程序的运算速度
我们可以从上述问题可以大概看出，在计算数据较少时，如只有100个数据时，简单查找法的时间最多为100ms，而二分法的时间最多只有7ms两者相差还不是很大，简单查找法的搜索时间是二分法的15倍，而一旦数据量扩大到40亿，则两者相差时间不可计数。由上可知，仅知道运行速度是不够的，我们还得知道增速，这时大O表示法就有了用武之地。
对于二分法的实际运用，只需要把一个low指向开始，一个high指向结束，将两者之和的一半mid与数对比，大了则将mid-1赋值给high，小了则把mid+1赋值给low，在重复就可以了。
因为文字所限只能谈到这里了，顺便说一种慢到无法形容的算法那就是旅行商问题的解决方案，运行时间为O（n！）。感觉无解。它说的是一个旅行商想去5个城市，他想保证自己去的路线是最短的，于是他分别列出5个成市的的所有路线，再计算其路程选出最短的路程，也就是要做5！次步骤总共120次，6个城市就要6！次（720次），7个城市就要5040次……
如果城市超过100个，连太阳都没有了。
|
|
收藏
淘帖
踩
