算法基础知识

算法基础知识1. 什么是算法算法是对特定问题求解步骤的一种描述它是指令的有限序列每一个指令都表示一个或多个操作。2. 算法的五大基本特性(必考概念)有穷性算法必须在执行有限步之后结束。确定性算法中的每一条指令必须有确切的含义不能有二义性。可行性算法中的操作都是可以通过已经实现的基本运算执行有限次来实现的。输入一个算法有零个或多个输入。输出一个算法有一个或多个输出。3. 优秀算法的评价标准正确性能满足具体问题的需求。健壮性当输入非法数据时算法能做出适当反应或处理。高效性执行时间短(时间复杂度低)占用内存少(空间复杂度低)。4. 算法分类基础算法是解决各类计算问题的基石通常可以分为以下几大类排序算法将一组数据按照特定顺序重新排列。常见的有冒泡排序、快速排序、归并排序和堆排序等。搜索算法在数据结构中查找特定元素。常见的包括线性搜索、二分搜索以及图算法中的深度优先搜索(DFS)和广度优先搜索(BFS)。分治算法将复杂问题分解为几个规模较小的子问题递归解决后再合并结果。归并排序和快速排序是其典型应用。动态规划通过将复杂问题拆解为重叠子问题并存储子问题的解来避免重复计算常用于解决最优化问题(如背包问题、最长公共子序列)。贪婪算法(贪心算法)在每一步选择中都采取当前状态下最优的选择期望最终达到全局最优。常用于任务调度、霍夫曼编码等问题。回溯算法通过探索所有可能的分支来寻找解若分支不包含可行解则进行“剪枝”退回。常用于八皇后问题、图的着色问题等组合问题。分支限界算法在回溯算法的基础上使用优先队列加速分支选择适用于旅行商问题(TSP)等大规模优化问题。