算法复杂度和解空间
文章目录
线性代数中,印象最深刻的是矩阵变换、求矩阵秩的算数细节,这些细节曾经让本科时的我迷失于学习的细节中。大多数学生跟我一样,被课程的莫名其妙搞的晕头转向,丧失了直觉性的教学使得学生感觉莫名其妙。
今天我才发现线性代数给我带来的的最大的改变其实是一种思维方式,用向量和线性空间来解释世界和解决问题。
算法本质上是在一个解空间中的搜索问题。
一维排序算法的解空间就是所有的下标排列组合,n个元素的n!种排列组合也就是说解空间是n维向量空间,我们要找到一个点,那个点就是排序的过程。排序的过程基于比较,完美情况下,每一次两个元素的比较都可以从解空间中排除掉一半的向量,每次比较都可以二分的话,复杂度就是O(nlog(n))。
01背包问题的解空间,首先看第一个物品要不要选,这就有了选或不选两个分支,每个分支都是一个更低阶的子问题,递归下去是一个2^n个叶子节点的树,从根节点到每个叶子节点的路径010101101串就对应一个解,其中每个分叉都对应选或者不选。当确定了一个节点之后,随之而来的是解空间中有一半的点被排除掉了,每次解空间折半的时间复杂度是O(W),这样的话就是O(nW)了。
高效的算法一定是高效的探索解空间,通过高效的方式,每次子计算应该尽可能缩小探索到的解空间的交集。先拿物品i和先拿物品j这两个分支里面存在着大量的重复,定义子问题的原则就是建立递归公式的时候将解空间进行不交的切分。
充分利用每一次计算得到的信息,尽可能的缩小解空间。
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论