温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

算法解题思路是什么

发布时间:2022-02-18 16:20:27 来源:亿速云 阅读:147 作者:zzz 栏目:开发技术

这篇“算法解题思路是什么”文章的知识点大部分人都不太理解,所以小编给大家总结了以下内容,内容详细,步骤清晰,具有一定的借鉴价值,希望大家阅读完这篇文章能有所收获,下面我们一起来看看这篇“算法解题思路是什么”文章吧。

算法解题思路是什么

分析框架

1、以算法输入规模n作为参数进行分析算法效率

2、时间复杂度:找出基本操作O(1),再计算它的运行次数(忽略乘法常量,仅关注增长次数)

3、增长次数:log2n

4、最差、平均和最佳效率均是指输入规模为n时候的效率(平均效率可以引用已知的推到结果)

主要概括分析框架:

1、算法的时间效率和空间效率都用输入规模的函数进行度量。

2、用算法的基本操作的执行次数来度量时间效率,用算法消耗的额外单位的数量来度量空间单位

3、在输入规模相同的情况下,有写算法的效率会有显著的差异,对于这类算法需要分析最差、平均和最佳效率

4、框架主要关心:输入规模趋向于无限大的情况下它的效率问题

渐近符号和基本效率类型

1、O(g(n))是增长次数

2、Ω(g(n))是增长次数 >= c*g(n)的函数集合,下阶

3、θ(g(n))是增长次数 = c*g(n)的函数集合,同阶

可以利用极限进行比较增长次数(洛必达法则)算法整体效率是由具有较大增长次数的部分所决定的。

非递归问题的数学分析的通用方案

1、决定哪个参数表示输入规模的度量标准

2、找出算法的基本操作

3、检查基本操作的执行次数是否只依赖于输入规模,如果它还依赖于一些其他的特性(例如:元素在数组中的位置等)则分析最差、平均和最佳效率

4、建立一个算法基本操作执行次数的求和表达式(有可能是递推表达式)

5、利用求和运算的标准运算或者法则来建立一个操作次数的闭合公式,或者至少确定它的增长次数

递归问题的数学分析的通用方案

1、决定哪个参数表示输入规模的度量标准

2、找出算法的基本操作

3、检查基本操作的执行次数是否只依赖于输入规模,如果它还依赖于一些其他的特性(例如:元素在数组中的位置等)则分析最差、平均和最佳效率

4、对于算法基本操作执行次数,建立一个递推关系以及相应的初始条件。

5、解这个递推式,或者至少确定它的增长次数。

以上就是关于“算法解题思路是什么”这篇文章的内容,相信大家都有了一定的了解,希望小编分享的内容对大家有帮助,若想了解更多相关的知识内容,请关注亿速云行业资讯频道。

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI