算法基础概念

2020-07-01  本文已影响0人  借缕春风绽百花

1.算法的定义

算法是解决某个问题的特定的指令序列。

2.算法四个性质:

①输入
②输出
③确定性
④有限性

3.算法的本质

算法的本质是解决问题的方法

4.算法的优势

①把复杂的事交给计算机完成
②一个算法可以解决一类问题

5.算法的核心任务

核心任务是设计合理的算法

6.算法的描述方式

自然语言
数学公式
流程图
伪代码
程序设计语言

7.好的算法具有的特点

正确性(Correctness)
有效性(Efficiency)
时间有效性(Time efficiency)
空间有效性(Space efficiency)
易理解(Understandability)
易实现(Implementability)
通用性(Generaty)

8.时间有效性

通常使用时间复杂度和空间复杂度来衡量算法的时间有效性和空间有效性。

8.1时间有效性衡量标准

运行时间

优点:最直接地反映算法的时间复杂度。
缺点:
①机器依赖,不同机器运行时间不同。
②缺乏解释,未回答不同程序的时间差异。

时间复杂度

使用基本运算(加,减,乘,除,判断,数组存取,函数调用)的发生次数来衡量。

优点:与机器无关,具有解释力。
缺点:
①统计基本运算次数工作繁琐。
②算法时间复杂度主要由输入规模决定,关键式增长量级,增长函数不是那么重要。

近似表示:
O(f(n)):算法运行时间的上界,也就是最坏情况下的时间复杂度;

Ω(f(n)):算法运行时间的下界,也就是最好情况下的时间复杂度;

Θ(f(n)):算法运行时间的上界和下界,这里Θ(f(n))是渐近的确界,
另外,并非所有的算法都有Θ(f(n))。

时间复杂度的增长量级(从小大排列)

O(1) constant time 常数级
O(log n) logarithmic time 对数级
O(n) linear time 线性级
O(nlog n)
O(n^2) quatdratic time 平方级
O(n^k) polynomial time 多项式级
O(2^n) exponential time 指数级
O(n!) factorial time 阶乘级

算法复杂度的三种情形

最好情形
最坏情形
平均情形

9.算法设计模式

① 暴力求解(Brute force)
②分治法(Divide and conquer)
③贪婪算法(Greedy approach)
④动态规划(Backtracking)
⑤回溯法(Branch and bound)
⑥分支界限法(Randomized algorithm)
⑦概率算法(randomized algorithm)

10.算法思维

现实问题——>形式化描述——>设计算法——>方案实施——>现实问题

上一篇 下一篇

猜你喜欢

热点阅读