Java教程

【基础】基础算法学习笔记(状态空间)

本文主要是介绍【基础】基础算法学习笔记(状态空间),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

基础算法学习笔记(状态空间)

一、状态空间

1、定义(什么是状态空间):一个实际问题的各种可能情况构成的集合。(解释:为什么需要算法来和程序来处理问题?如果一道题可以手算得到答案,换句话说就是存在通过代入某个数学式子就直接得到答案的,那么这道题就不是一道算法题,或者他的解直接就是O(1)的。那算法和程序题还有什么意义呢。但是实际是现实生活中我们的很多问题都不是可以直接计算的,我们往往只能大致确定一个范围,然后在这个范围之中再去逐一排除不可行不够优的答案,得到最终答案。这些在逐一判断之前不能确定,都有可能成为答案的解构成的集合就是状态空间。)

2、与基础算法的关系:通过划分,归纳,提取,抽象来帮助提高程序遍历状态空间的效率。

  • 遍历方式(程序语法上的实现):递推(循环for),递归(函数)
  • 遍历顺序:模拟(问题的直接表述形式),枚举(大多都是线性的方式),搜索(形成一颗搜索树解答树,带有一定的选择性决策性)
  • 遍历过程中的决策方法:贪心(每步决策时采取局部最策略,当前意义下,局部约束条件下的最优解),DP(基于全局考量的分阶段,按维度,无重复的遍历)
  • 状态空间中各状态的映射方式:二分,倍增,排序。(划分,等价,代表)

3、状态空间的一些特点

  • 规模大小(时空复杂度)
    • 多项式,nk,k为常数nk,k为常数 ,递推
    • 指数,kn,k为常数kn,k为常数 ,递归|位运算
    • 排列,n!n! ,递归|next_permutation
    • 组合,CmnCnm ,递归+剪枝
  • 占坑待填

二、基础算法

1、分类:枚举,模拟,搜索,递推,递归,二分,倍增,贪心,DP等。
2、作为基础算法,简单易懂却又蕴含着巧妙而深刻的思想。
3、作为构建算法与数据结构体系的基本单位,贯穿整个程序设计竞赛的始末。
4、对于理解后面的复杂算法有着极大的帮助,也对创造新算法具有重要作用。

三、常说的暴力指的是

模拟,枚举,搜索。
(理论上讲所有算法都是暴力。)
(yql说,NOIP暴力能打到580分。)

这篇关于【基础】基础算法学习笔记(状态空间)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!