算法-基础

请设置文章作者

发布于：2020年7月15日

次浏览

算法的基本要素

1. 对数据对象的运算和操作
2. 算法的控制结构

朴素模式匹配算法

斐波那契数列

不能使用递归f(n) = f(n-1) + f(n-2)的原因：会造成大量重复计算，导致时间复杂度为O(2^n)。

使用动态规划消除重复计算，可使时间复杂度优化至O(n)。可用数组保存计算结果，则空间复杂度为O(n)。此处进一步简化，只使用两个变量保存结果，因此空间复杂度为O(1)。

1
2
3
4
5
6
7
8
9

class Solution {
    public int fib(int N) {
        int curr = 0, next = 1;
        while(N-- > 0) {
            next = next + curr;
            curr = next - curr;
        }
        return curr;
    }

约瑟夫环

在对问题的解空间树进行搜索的方法中，一个结点有多次机会成为活结点的是回溯法

分支限界思想：

1. 以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树
2. 分支限界法中，每一个活结点只有一次机会成为扩展结点，活结点一旦成为扩展结点，就一次性产生其所有儿子结点，其中导致不可行解或导致非最优解的儿子结点被舍弃其余儿子结点被加入活结点表中
3. 然后从活结点表中取下一结点成为扩展结点
4. 重复上述结点扩展过程，直至到找到所需要的解或活结点表为止

广度优先且不满足的被舍弃，满足的找其儿子结点，所以其不可能再次成为活结点。

回溯法：深度优先自然可以回到此节点。