每个程序员都应该知道的算法

淡淡的烟草味﹌ 2022-10-30 12:26 243阅读 0赞

在学习算法的过程中，我们除了要了解某个算法的基本原理、实现方式，更重要的一个环节是利用big-O理论来分析算法的复杂度。在时间复杂度和空间复杂度之间，我们又会更注重时间复杂度。

时间复杂度按优劣排差不多集中在：

O(1), O(log n), O(n), O(n log n), O(n2), O(nk), O(2n)

## 二分查找法 ##

**概念：**

在计算机科学中，二分搜索（binary search），也称折半搜索（half-interval search）、对数搜索（logarithmic search），是一种在**有序数组**中查找某一特定元素的搜索算法。

而想要应用二分查找法，这“一堆数”必须有以下特征：

*  存储在数组中
 *  有序排列

**实现：**

搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

![f4d99189e4450e58aaca28568f939367.gif][]

/** * 二分查找递归实现。 * @param srcArray 有序数组 * @param start 数组低地址下标 * @param end 数组高地址下标 * @param key 查找元素 * @return 查找元素不存在返回-1 */
        public static int binSearch(int srcArray[], int start, int end, int key) { 
            int mid = (end - start) / 2 + start;
            if (srcArray[mid] == key) { 
                return mid;
            }
            if (start >= end) { 
                return -1;
            } else if (key > srcArray[mid]) { 
                return binSearch(srcArray, mid + 1, end, key);
            } else if (key < srcArray[mid]) { 
                return binSearch(srcArray, start, mid - 1, key);
            }
            return -1;
        }

**时间复杂度：**

O(log n)

## 二叉树深度优先搜索(DFS) ##

**概念：**

深度优先搜索算法（Depth-First-Search），是搜索算法的一种。它沿着树的深度遍历树的节点，尽可能深的搜索树的分 支。  
当节点v的所有边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。  
这一过程一直进行到已发现从源节点可达的所有节点为止。  
如果还存在未被发 现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。  
深度优先搜索是图论中的经典算法，利用深度优先搜索算法可以产生目标图的相应拓扑排序表，利用拓扑排序表可以方便的解决很多相关的图论问题，如最大路径问题等等。一般用堆数据结构来辅助实现DFS算法。

**实现：**

DFS 在访问图中某一起始顶点 v 后，由 v 出发，访问它的任一邻接顶点 w1；再从 w1 出发，访问与 w1邻 接但还没有访问过的顶点 w2；然后再从 w2 出发，进行类似的访问，… 如此进行下去，直至到达所有的邻接顶点都被访问过的顶点 u 为止。  
接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它没有被访问的邻接顶点。如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。

![4dedce3077fa6236da69d4057305e014.gif][]

例如下图，其深度优先遍历顺序为 1->2->4->8->5->3->6->7

![f78793fa48a2a6fd0dff0d06240149f3.png][]

**时间复杂度：**

O(N ^ 2)

## 二叉树广度优先搜索(BFS) ##

**概念：**

广度优先搜索算法（Breadth-First-Search），是一种图形搜索算法，简单的说，BFS是从根节点开始，沿着树(图)的宽度遍历树(图)的节点。如果所有节点均被访问，则算法中止。  
BFS同样属于盲目搜索。  
一般用队列数据结构来辅助实现BFS算法。

**实现：**

1 首先将根节点放入队列中。

2 从队列中取出第一个节点，并检验它是否为目标。如果找到目标，则结束搜寻并回传结果。否则将它所有尚未检验过的直接子节点加入队列中。

3 若队列为空，表示整张图都检查过了——亦即图中没有欲搜寻的目标。结束搜寻并回传“找不到目标”。

4 重复步骤2。

![b3ad957ca806afee57d84d56b3fffa8f.gif][]

例如下图，其广度优先算法的遍历顺序为：1->2->3->4->5->6->7->8

![f78793fa48a2a6fd0dff0d06240149f3.png][]

**时间复杂度：**

O(N + M)

## DFS & BFS示例代码 ##

package com.uaf.nlp.pay.utils.wxsdk;
    
    import java.io.IOException;
    import java.util.Scanner;
    
    public class ListDG { 
    	// 邻接表中表对应的链表的顶点
    	private class ENode { 
    		int ivex;       // 该边所指向的顶点的位置
    		ENode nextEdge; // 指向下一条弧的指针
    	}
    
    	// 邻接表中表的顶点
    	private class VNode { 
    		char data;          // 顶点信息
    		ENode firstEdge;    // 指向第一条依附该顶点的弧
    	}
    
    	;
    
    	private VNode[] mVexs;  // 顶点数组
    
    	/* * 创建图(自己输入数据) */
    	public ListDG() { 
    
    		// 输入"顶点数"和"边数"
    		System.out.printf("input vertex number: ");
    		int vlen = readInt();
    		System.out.printf("input edge number: ");
    		int elen = readInt();
    		if (vlen < 1 || elen < 1 || (elen > (vlen * (vlen - 1)))) { 
    			System.out.printf("input error: invalid parameters!\n");
    			return;
    		}
    
    		// 初始化"顶点"
    		mVexs = new VNode[vlen];
    		for (int i = 0; i < mVexs.length; i++) { 
    			System.out.printf("vertex(%d): ", i);
    			mVexs[i] = new VNode();
    			mVexs[i].data = readChar();
    			mVexs[i].firstEdge = null;
    		}
    
    		// 初始化"边"
    		//mMatrix = new int[vlen][vlen];
    		for (int i = 0; i < elen; i++) { 
    			// 读取边的起始顶点和结束顶点
    			System.out.printf("edge(%d):", i);
    			char c1 = readChar();
    			char c2 = readChar();
    			int p1 = getPosition(c1);
    			int p2 = getPosition(c2);
    			// 初始化node1
    			ENode node1 = new ENode();
    			node1.ivex = p2;
    			// 将node1链接到"p1所在链表的末尾"
    			if (mVexs[p1].firstEdge == null)
    				mVexs[p1].firstEdge = node1;
    			else
    				linkLast(mVexs[p1].firstEdge, node1);
    		}
    	}
    
    	/* * 创建图(用已提供的矩阵) * * 参数说明： * vexs -- 顶点数组 * edges -- 边数组 */
    	public ListDG(char[] vexs, char[][] edges) { 
    
    		// 初始化"顶点数"和"边数"
    		int vlen = vexs.length;
    		int elen = edges.length;
    
    		// 初始化"顶点"
    		mVexs = new VNode[vlen];
    		for (int i = 0; i < mVexs.length; i++) { 
    			mVexs[i] = new VNode();
    			mVexs[i].data = vexs[i];
    			mVexs[i].firstEdge = null;
    		}
    
    		// 初始化"边"
    		for (int i = 0; i < elen; i++) { 
    			// 读取边的起始顶点和结束顶点
    			char c1 = edges[i][0];
    			char c2 = edges[i][1];
    			// 读取边的起始顶点和结束顶点
    			int p1 = getPosition(edges[i][0]);
    			int p2 = getPosition(edges[i][1]);
    
    			// 初始化node1
    			ENode node1 = new ENode();
    			node1.ivex = p2;
    			// 将node1链接到"p1所在链表的末尾"
    			if (mVexs[p1].firstEdge == null)
    				mVexs[p1].firstEdge = node1;
    			else
    				linkLast(mVexs[p1].firstEdge, node1);
    		}
    	}
    
    	/* * 将node节点链接到list的最后 */
    	private void linkLast(ENode list, ENode node) { 
    		ENode p = list;
    
    		while (p.nextEdge != null)
    			p = p.nextEdge;
    		p.nextEdge = node;
    	}
    
    	/* * 返回ch位置 */
    	private int getPosition(char ch) { 
    		for (int i = 0; i < mVexs.length; i++)
    			if (mVexs[i].data == ch)
    				return i;
    		return -1;
    	}
    
    	/* * 读取一个输入字符 */
    	private char readChar() { 
    		char ch = '0';
    
    		do { 
    			try { 
    				ch = (char) System.in.read();
    			} catch (IOException e) { 
    				e.printStackTrace();
    			}
    		} while (!((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z')));
    
    		return ch;
    	}
    
    	/* * 读取一个输入字符 */
    	private int readInt() { 
    		Scanner scanner = new Scanner(System.in);
    		return scanner.nextInt();
    	}
    
    	/* * 深度优先搜索遍历图的递归实现 */
    	private void DFS(int i, boolean[] visited) { 
    		ENode node;
    
    		visited[i] = true;
    		System.out.printf("%c ", mVexs[i].data);
    		node = mVexs[i].firstEdge;
    		while (node != null) { 
    			if (!visited[node.ivex])
    				DFS(node.ivex, visited);
    			node = node.nextEdge;
    		}
    	}
    
    	/* * 深度优先搜索遍历图 */
    	public void DFS() { 
    		boolean[] visited = new boolean[mVexs.length];       // 顶点访问标记
    
    		// 初始化所有顶点都没有被访问
    		for (int i = 0; i < mVexs.length; i++)
    			visited[i] = false;
    
    		System.out.printf("DFS: ");
    		for (int i = 0; i < mVexs.length; i++) { 
    			if (!visited[i])
    				DFS(i, visited);
    		}
    		System.out.printf("\n");
    	}
    
    	/* * 广度优先搜索（类似于树的层次遍历） */
    	public void BFS() { 
    		int head = 0;
    		int rear = 0;
    		int[] queue = new int[mVexs.length];            // 辅组队列
    		boolean[] visited = new boolean[mVexs.length];  // 顶点访问标记
    
    		for (int i = 0; i < mVexs.length; i++)
    			visited[i] = false;
    
    		System.out.printf("BFS: ");
    		for (int i = 0; i < mVexs.length; i++) { 
    			if (!visited[i]) { 
    				visited[i] = true;
    				System.out.printf("%c ", mVexs[i].data);
    				queue[rear++] = i;  // 入队列
    			}
    
    			while (head != rear) { 
    				int j = queue[head++];  // 出队列
    				ENode node = mVexs[j].firstEdge;
    				while (node != null) { 
    					int k = node.ivex;
    					if (!visited[k]) { 
    						visited[k] = true;
    						System.out.printf("%c ", mVexs[k].data);
    						queue[rear++] = k;
    					}
    					node = node.nextEdge;
    				}
    			}
    		}
    		System.out.printf("\n");
    	}
    
    	/* * 打印矩阵队列图 */
    	public void print() { 
    		System.out.printf("List Graph:\n");
    		for (int i = 0; i < mVexs.length; i++) { 
    			System.out.printf("%d(%c): ", i, mVexs[i].data);
    			ENode node = mVexs[i].firstEdge;
    			while (node != null) { 
    				System.out.printf("%d(%c) ", node.ivex, mVexs[node.ivex].data);
    				node = node.nextEdge;
    			}
    			System.out.printf("\n");
    		}
    	}
    
    	public static void main(String[] args) { 
    		char[] vexs = {  'A', 'B', 'C', 'D', 'E', 'F', 'G' };
    		char[][] edges = new char[][] {  {  'A', 'B' }, {  'B', 'C' }, {  'B', 'E' }, {  'B', 'F' }, {  'C', 'E' },
    				{  'D', 'C' }, {  'E', 'B' }, {  'E', 'D' }, {  'F', 'G' } };
    		ListDG pG;
    
    		// 自定义"图"(输入矩阵队列)
    		//pG = new ListDG();
    		// 采用已有的"图"
    		pG = new ListDG(vexs, edges);
    
    		pG.print();   // 打印图
    		pG.DFS();     // 深度优先遍历
    		pG.BFS();     // 广度优先遍历
    	}
    }

**输出结果：**

List Graph:
    0(A): 1(B) 
    1(B): 2(C) 4(E) 5(F) 
    2(C): 4(E) 
    3(D): 2(C) 
    4(E): 1(B) 3(D) 
    5(F): 6(G) 
    6(G): 
    DFS: A B C E D F G 
    BFS: A B C E F D G

总的来说，BFS多用于寻找最短路径的问题，DFS多用于快速发现底部节点。

--------------------

欢迎关注公众号： **编码是个技术活**

![在这里插入图片描述][20210219162337578.jpg_pic_center]

[f4d99189e4450e58aaca28568f939367.gif]: /images/20221024/54a6761b4d7c45a7a9704e15bf892d44.png
[4dedce3077fa6236da69d4057305e014.gif]: /images/20221024/8d995c4e7bf0494c96df091265747925.png
[f78793fa48a2a6fd0dff0d06240149f3.png]: /images/20221024/42d99a14c6114f378b48bad5d2be7df8.png
[b3ad957ca806afee57d84d56b3fffa8f.gif]: /images/20221024/bed71de67a5f4e37a6e58d96c7ffa1aa.png
[20210219162337578.jpg_pic_center]: /images/20221024/6359e7a433354172b55126ec57edcca6.png