高级算法设计与分析(一) -- 算法引论

2023-12-20 08:39:20

系列文章目录

高级算法设计与分析(一) -- 算法引论

未完待续【

高级算法设计与分析(二) -- 递归与分治策略

高级算法设计与分析(三) -- 动态规划

高级算法设计与分析(四) -- 贪心算法

高级算法设计与分析(五) -- 回溯法

高级算法设计与分析(六) -- 分支限界法

高级算法设计与分析(七) -- 概率算法

高级算法设计与分析(八) -- NP完全性理论

高级算法设计与分析(九) -- 总结


目录

系列文章目录

前言

一、算法与程序

1、算法

2、程序

3、思算法的基本特征

3.1、输入(0~N个)

3.2、输出(1~N个)

3.3、确定性

3.4、有限性

二、表达算法的抽象机制

1、数据

2、运算

3、算法用程序描述的基本方法

三、算法的复杂性分析

1、时间复杂度与空间复杂度(对资源的消耗)

2、复杂度的计算

3、复杂性渐进态(次数最高的那一项)

3.1、O(order)的定义

3.1.1、O的运算规则

3.3.2、O的实质

3.3.3、O的理解

3.2、Ω和θ

习题


前言

tips:鉴于本人写字如画符,就不出视频教程了,如实在有需要,请在文章下方留言。当然,文章有任何问题,也请留言,谢谢!

这个系列用另一种形式,把习题放在最下面,看看好用不。

本系列文章最后一文会进行简要全部总结,以及思维导图放在最后一篇文章最下面,请自行获取。


一、算法与程序

1、算法

指解决问题的方法或过程。

2、程序

算法用某种程序设计语言的具体实现。

3、思算法的基本特征

3.1、输入(0~N个)

0个输入的算法不具有通用性,但有用,如计算Π

3.2、输出(1~N个)

不可能没有输出(结果)

3.3、确定性

指令清晰、无歧义,但并不表示每次运行算法都会获得同样结果,如并行算法

3.4、有限性

每条指令执行次数、执行每条指令时间均有限,因此算法所需总时间也有限

二、表达算法的抽象机制

1、数据

基本数据:布尔值、字符、整数、浮点数等。矩阵、集合等较复杂数据均由基本数据构成。

2、运算

逻辑运算、关系运算、矩阵运算等
a=1; b=2; a>b
Matlab(Matrix laboratory)就是以矩阵运算为基础

3、算法用程序描述的基本方法

自顶向下,逐步求精

三、算法的复杂性分析

1、时间复杂度与空间复杂度
(对资源的消耗)

记法:T = T(N, I, A)或T(A) = T(N, I)或T=T(N, I)

含义:算法A的时间复杂度由问题规模(N)和输入(I)确定

2、复杂度的计算

3、复杂性渐进态
(次数最高的那一项)

3.1、O(order)的定义

3.1.1、O的运算规则

3.3.2、O的实质

3.3.3、O的理解

3.2、Ω和θ

O:不高于
Ω:不低于
θ:等于(阶数相等)

O:不高于 ? ? ? ? ? ? ? ? ? o:小于
Ω:不低于 ? ? ? ? ? ? ? ? ? ω:大于
θ:等于(阶数相等)


习题

topic(1):

!!! 20n>n^(2/3)

topic(2):

topic(3):

topic(4):

文章来源:https://blog.csdn.net/zqx1473/article/details/135079309
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。