选择题考点:
时间复杂性从低到高的顺序是?
问题: 有一个算法, 它的时间复杂性T(n)的递归定义如下, 问T(n)是?
下面哪些内容不是算法设计之前要完成的内容?
使用何种计算机语言设计程序
在算法设计与分析过程中,有算法设计,算法的正确性证明,算法的复杂性分析,程序设计等几个重要步骤,下面哪种顺序是正确的?
算法设计->算法的正确性证明->算法的复杂性分析->程序设计
算法的五个基本性质:
有穷性(Finiteness):算法必须在执行有限次后终止,不能无限循环下去。
确定性(Definiteness):在任何情况下,算法的每个步骤都应该有确切的定义,不能有二义性。
输入(Input):算法必须有零个或多个输入。可以没有输入。
输出(Output):算法必须有一个或多个输出,且与输入有某种特定关系。
可行性(Feasibility):算法中所描述的操作必须是可以实现的,即可以计算机程序的形式实现。
实现最大子序列的和上升子序列的两个子序列,动态规划
贪心算法:电影,异地开会
二分查找法:采用分治策略,分治采用递归策略
广度优先搜索:分治界限法
深度优先搜索:回溯
枚举算法的使用范围:解的个数有限的问题
100个数最少猜7次
快速幂分析程序的时间复杂度
快速幂算法是一种利用二进制分解来快速计算幂的算法,其时间复杂度为 O(log n)。
具体来说,如果要计算 a 的 n 次幂,通过二进制分解 n,可以将 a 的 n 次幂表示为 a 的若干个幂次的积,例如:
a^n = a^(2^0b0) * a^(2^1b1) * a^(2^2b2) * ... * a^(2^kbk)
其中,b0, b1, ..., bk 是 n 的二进制拆分后的系数。有了这个公式,我们就可以通过连续平方和取模来高效地计算 a 的 n 次幂:
分治法,贪心算法,动态规划算法解决问题的关键要素,特征
下面是这三种方法的关键要素和特征:
分治法
关键要素:把一个大问题分成若干个小问题,然后把小问题合并起来得到大问题的解。
特征:
适用于可分解成若干个相同子问题的问题。
每一次划分都将原问题的规模缩小为原来的一半或多个子问题。
子问题之间相互独立,不存在重叠子问题。
贪心算法
关键要素:每次都做出最好的选择。
特征:
适用于求局部最优解的问题。
每次贪心选择都会使当前状态优化到全局最优。
无法保证一定能得到全局最优解。
动态规划算法
关键要素:通过分解问题,将问题分成若干子问题,逐步求解得到原问题的解。
特征:
适用于具有重叠子问题和最优子结构性质的问题。
将重复计算的子问题缓存,避免重复计算。
从底向上逐步推导出原问题的解。
总的来说,选择哪种算法要根据问题本身的性质和规模进行考虑。对于可以分解成子问题的问题,可以采用分治法和动态规划算法;对于局部最优解有逼近全局最优解趋势的问题,可以采用贪心算法。在实际问题中,可以根据问题的特点进行综合考虑,选择适合的算法。
二分查找
二分查找也被称作折半查找,是一种非常高效的查找算法。它的基本思想是:对于已经排好序的数组,通过将数组不断地拆分为两半,确定查找元素可能在哪个子数组中,从而快速缩小查找范围,最终得到查找元素的位置。
具体实现步骤如下:
确定数组中间位置 mid,若查找元素等于中间位置的元素,则直接返回 mid。
若查找元素小于中间位置的元素,则在数组左半部分继续进行查找。
若查找元素大于中间位置的元素,则在数组右半部分继续进行查找。
重复以上步骤,直到找到查找元素或者确定查找范围为空,此时查找失败。
最优子结构性质的含义(问题的最优解包含它所有的最优解)
最优子结构性质只是表示问题的最优解可以通过其子问题的最优解来求得,而不是表示问题的最优解一定包含所有子问题的最优解。
解决迷宫问题和找牛问题:广度优先搜索
解决问题安排问题 : 贪⼼算法
递归定义 (⽤公式算时间复杂度)
哪种排序时间复杂度最低,在最坏情况下 :
归并排序
判断题考点:
对于问题的一个实例,如果算法能够获得正确的结果,就证明算法是正确的。×
使⽤⼆分搜索算法在 n个有序数中搜索⼀个给定的元素
最好时间复杂度 : O(1 )
最坏 : O(logn)
算法复杂度:时间空间复杂度,⽤时间复杂度衡量算 …好坏
零钱⾮零问题 : 贫⼼算法
零钱非零问题,也称为找零钱问题,是一个经典的问题,它的目标是找到一种最少的硬币组合,使得组合中硬币总面值等于要找的零钱数。
贪心算法是解决这种找零钱问题的一种常用方法,被称为贪心找零钱算法。这个算法的基本思想是,从面额最大的硬币开始,取尽可能多的这种硬币,直到凑出所需要的零钱数,再在剩余的金额中重复上述过程。这个过程的关键在于每次都取最大的硬币,以达到最小化硬币数量的效果。
满足最优子结构性质必定满足贪心选择性质
错的
这个结论是不准确的。虽然贪心算法和满足最优子结构性质的问题都与局部最优解有关,但两者之间并没有必然的联系。具体来说,满足最优子结构性质的问题需要满足一个子问题最优解能够推导出原问题最优解的特点。而贪心选择性质则是指在求解问题时,采取局部最优解可以得到全局最优解的情况下,贪心算法才能正确地求解问题。
任何一个算法包含的子结构有限程序需要
错的
简答题考点:
贪心算法
贪心算法是一种把原问题分解成一系列子问题,并选择最优子问题的算法。
它的基本思想是通过每个阶段的局部最优选择来达到全局最优解。
贪心算法通常应用于问题的最优化求解,如最短路径、最小生成树等。
解题步骤:
(1)将问题分解为若干个子问题;
(2)确定每个子问题中需要做出的局部最优决策;
(3)将每个局部最优决策合并为全局最优解。
动态规划
动态规划是一种适用于具有重叠子问题和最优子结构性质的问题的算法思想。
它的基本思想是将原问题分解为若干个子问题,并保存每个子问题的解,避免重复计算。
通常用于求解最长公共子序列、最短路径、背包问题等。
解题步骤:
(1)确定状态:设计状态表示方法,定义状态转移方程;
(2)初始状态:对边界情况进行初始化;
(3)状态转移:利用之前的状态推出当前状态的值;
(4)返回结果:根据最终状态给出结果。
二分查找
二分查找是一种基于比较目标值和数组中间点的元素来实现的算法思想。
它通常适用于有序数组中查找特定元素的问题,具有时间复杂度为O(log n)的优势。
解题步骤:
(1)确定区间:通过左右指针确定查找区间;
(2)取中间值:求出区间的中间位置,取出中间值;
(3)比较并更新区间端点:将中间值与目标值进行比较,并更新左右指针所在区间的端点;
(4)重复执行直到找到或不存在目标值为止。
分治法
分治法是一种将大问题分解成若干个相互独立的子问题,并递归求解这些子问题,最后将子问题的解合并成原问题的解的算法思想。
它通常应用于排序、搜索、计算几何等问题。
解题步骤:
(1)分解问题:将原问题分解成若干个规模较小且结构相似的子问题;
(2)求解子问题:递归地求解每个子问题的解;
(3)合并子问题的解:将每个子问题的解合并为原问题的解。
算法设计的实现考点:
动态规划
贪心算法
枚举
标签:复习,复杂度,问题,算法,查找,最优,贪心 From: https://www.cnblogs.com/dslyyy/p/17487359.html