16 Feb 2019

算法从入门到去世

算法从入门到去世

  • 算法的度量

    • Big O

      如果存在正数c和N,对于所有的\(n>=N\),有\(f(n)<=cg(n)\),则\(f(n)=O(g(n))\)

      Big O 是一个算法最坏情况的度量

    • Big Omega

      如果存在正数c和N,对于所有的\(n>=N\),有\(f(n)>=cg(n)\),则\(f(n)=Ω(g(n))\)

      Big Omega 是一个算法最好情况的度量

    • Big Theta

      如果存在正数c1,c2和N,对于所有的\(n>=N\),有\(c1g(n)<=f(n)<=c2g(n)\),则\(f(n)=θ(g(n))\)

      Big Theta 表达了一个算法的区间

    常用Big O

  • Big O分析

    常见的输入输出以及简单的赋值语句,可以认为时间复杂度是 \(O(1)\)

    计算复杂度时乘以一个常数复杂度不变,即\(O(cf(n))=O(f(n))\)

    程序的基本结构有三种,顺序结构,选择机构,循环结构

    • 计算复杂度的基本法则
      • 顺序结构

        通过求和法则来进行计算

        算法的两个部分时间复杂度分别为 \(T1(n)=O(f(n))\) 和 \(T2(n)=O(g(n))\),则\(T1(n)+T2(n)=O(max(f(n),g(n)))\)

        算法的 两 个部分时间复杂度分别为 \(T1(m)=O(f(m)) 和 T2(n)=O(g(n))\),则

        \[T1(m)+T2(n)=O(f(m)+g(n))\]
      • 选择结构

        判断条件的时间复杂度为 \(O(1)\)

      • 循环结构

        使用乘法法则

        若两个部分时间复杂度分别为 \(T1(n)=O(f(n))\) 和 ,\(T2(n)=O(g(n))\)则 \(T1T2=O(f(n)g(n))\)

        例:

        int function(int n)
        {
            printf("hello,world\n");//1
            return 0;
        }//时间复杂度O(1)
              
        int function(int n)
        {
            for (int i = 0; i < n; ++i)//n
            {
                printf("hello,world\n");//1
            }
            return 0;
        }//时间复杂度O(n)
              
        int function(int n)
        {
            for (int i = 0; i < n; ++i)//n
            {
                for (int j = 0; j < n; ++j)//n
                {
                    printf("hello,world\n");//1
                }
            }
            return 0;
        }
        //时间复杂度O(n^2)
              
        int function(int n)
        {
            for (int i = 0; i < n; ++i)//n
            {
                for (int j = 0; j < n; ++j)//n
                {
                    printf("hello,world\n");//1
                    for(int k = 0; k < n; ++k)//n
                    {
                        printf("hello,world\n");//1
                    }
                }
            }
            return 0;
        }//时间复杂度O(n^3)
        
    • 递归的时间复杂度计算

      当一个算法中包含递归调用时,其时间复杂度的分析会转化为一个递归方程求解

      • 递归树法

        例:

        1

        2

        时间复杂度等于树高与每层数据量之和

      • 主定理法

        对于形如\(T(n) = aT(n/b) + f(n)\)的递归方程

        3

      • 迭代法

        把递归方程右边展开,直到没有可以迭代的项为止,通过对右边的和进行估算来估计方程的解

        对于递归方程T(n)=2T(n/2)+n2

        4

      • 代入法

        代入法的基本步骤是先推测递归方程的显式解,然后用数学归纳法来验证该解是否合理

  • 数据结构

    • 数组

      数组是可以在内存中连续存储多个元素的结构,在内存中的分配也是连续的,数组中的元素通过数组下标进行访问。

      • 优点:

        1、按照索引查询元素速度快 2、按照索引遍历数组方便

      • 缺点:

        1、数组的大小固定后就无法扩容了 2、数组只能存储一种类型的数据 3、添加,删除的操作慢,因为要移动其他的元素。

    • 链表

      链表是物理存储单元上非连续的、非顺序的存储结构,数据元素的逻辑顺序是通过链表的指针地址实现,每个元素包含两个结点,一个是存储元素的数据域 (内存空间),另一个是指向下一个结点地址的指针域。根据指针的指向,链表能形成不同的结构,例如单链表,双向链表,循环链表等。

      • 优点:

        1、链表是很常用的一种数据结构,不需要初始化容量,可以任意加减元素; 2、添加或者删除元素时只需要改变前后两个元素结点的指针域指向地址即可,所以添加,删除很快;

      • 缺点:

        1、因为含有大量的指针域,占用空间较大; 2、查找元素需要遍历链表来查找,非常耗时。

    • 栈是一种特殊的线性表,仅能在线性表的一端操作,栈顶允许操作,栈底不允许操作,先进后出。栈顶放入元素的操作称为入栈,取出元素称为出栈。

      • 支持的操作:

        push - 入栈

        peek - 查看栈顶

        pop - 弹出栈顶元素

      • 实现方式

        数组实现(需要一个变量来标记栈顶位置)

        链表实现(插入元素时注意对表头的操作 )

    • 队列

      队列与栈一样,也是一种线性表,不同的是,队列可以在一端添加元素,在另一端取出元素先进先出。从一端放入元素的操作称为入队列,取出元素称为出队列。

      • 支持的操作:

        Enqueue - 入队列

        Dequeue - 出队列

      • 实现方式

        数组实现(需要一个变量来标记队列头及队列尾的位置)

        链表实现(需要保存表尾,处理表头的时候注意操作顺序)

    • 树是一种能够分层存储数据的重要数据结构,是由n(n>=1)个有限节点组成一个具有层次关系的集合。树中的每个元素被称为树的节点,每个节点有若干个指针指向子节点。从节点的角度来看,树是由唯一的起始节点引出的节点集合。这个起始结点称为根(root)。树中节点的子树数目称为节点的度(degree)

      • 特点

        1、每个节点有零个或多个子节点;

        2、没有父节点的节点称为根节点;

        3、每一个非根节点有且只有一个父节点;

        4、除了根节点外,每个子节点可以分为多个不相交的子树;

      • 二叉树

        二叉树是一种常见的特殊的树

        • 特点

          1、每个结点最多有两颗子树,结点的度最大为2

          2、左子树和右子树有顺序,次序不能颠倒。

          3、即使某结点只有一个子树,也要区分左右子树。

    • 图由结点的有穷集合V和边的集合E组成

      • 有向图

        有向图的边具有指向性,即AB仅表示由A到B的路径,但并不意味着B可以连到A

      • 无向图

        无向图的每条边都表示一条双向路径。

        6

    • n个元素的序列\(\{k1,k2,ki,…,kn\}\)当且仅当满足下关系时,称之为堆。

      \((ki <= k2i,ki <= k2i+1)\)或者\((ki >= k2i,ki >= k2i+1), (i = 1,2,3,4...n/2)\)

      满足前者的表达式的称为小顶堆,满足后者表达式的称为大顶堆

      5

      堆可以被看做一棵树的数组对象,堆中某个节点的值总是不大于或不小于其父节点的值,堆总是一棵完全二叉树,将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆

    • 散列表

      散列表,也叫哈希表,是根据关键码(Key)和值(value)直接进行访问的数据结构,通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。

      若关键字为k,则其值存放在f(k)的存储位置上。称这个对应关系f为散列函数,按这个思想建立的表为散列表。

      对不同的关键字可能得到同一散列地址,即k1≠k2,而f(k1)=f(k2),这种现象称为冲突

  • 常用算法

    • 递归

      直接或者间接不断反复调用自身来达到解决问题的方法

    • 分治法

      把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题,直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。

      实质:递归求解

      • 分治法在每一层递归上的步骤
        1. 分解:将原问题分解为若干个规模较小,相互独立,与原问题形式相同的子问题
        2. 解决:若子问题规模较小而容易被解决则直接解,否则递归地解各个子问题
        3. 合并:将各个子问题的解合并为原问题的解
      • 适用条件
        1. 该问题的规模缩小到一定的程度就可以容易地解决
        2. 该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质
        3. 利用该问题分解出的子问题的解可以合并为该问题的解
        4. 该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子问题。

        具备1、2不具备3可以考虑贪心算法或动态规划

        4与分治法的效率有关,如果具备1、2、3不具备4可以考虑动态规划

    • 动态规划

      把多阶段过程转化为一系列单阶段问题,利用各阶段之间的关系,逐个求解。每次决策依赖于当前状态,又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的。

      初始状态→│决策1│→│决策2│→…→│决策n│→结束状态

      实质:分治思想和解决冗余。

      • 适用条件
        1. 最优子结构性质
        2. 某阶段状态一旦确定,就不受这个状态以后决策的影响。也就是说,某状态以后的过程不会影响以前的状态,只与当前状态有关,即无后效性
        3. 子问题之间是不独立的,一个子问题在下一阶段决策中可能被多次使用到。
      • 步骤
        1. 分析最优解的性质,并刻画其结构特征
        2. 递归的定义最优解
        3. 自底向上或自顶向下计算出最优值
        4. 根据计算最优值时得到的信息,构造问题的最优解
    • 贪心算法
      • 在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,所做出的是在某种意义上的局部最优解,从全局来说并不能保证总是最优。

      • 适用条件
        1. 最优子结构性质
        2. 每一个阶段的选择都是当前状态下的最优选择,即局部最优选择,并且最终能够求得问题的整体最优解,即具有贪心选择性质
      • 步骤
        1. 建立数学模型来描述问题
        2. 把求解的问题分成若干个子问题
        3. 对每一子问题求解,得到子问题的局部最优解
        4. 把子问题的解局部最优解合成原来解问题的一个解
    • 回溯法

      回溯法是一种搜索算法,从根节点出发,按照深度优先搜索的策略进行搜索,到达某一节点后 ,探索该节点是否包含该问题的解,如果包含则进入下一个节点进行搜索,若是不包含则回溯到父节点选择其他支路进行搜索

      • 步骤
        1. 针对所给的原问题,定义问题的解空间,问题的解空间应至少包含问题的一个(最优)解
        2. 确定易于搜索的解空间结构
        3. 以深度优先方式搜索解空间,并在搜索过程中用剪枝函数避免无效搜索
    • 分支界限法

      类似于回溯法,也是一种在问题的解空间树T上搜索问题解的算法。但在一般情况下,分支限界法与回溯法的求解目标不同。

      回溯法的求解目标是找出T中满足约束条件的所有解,而分支限界法的求解目标则是找出满足约束条件的一个解,或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解,即在某种意义下的最优解

      • 步骤
        1. 如果问题的目标为最小化,则设定目前最优解的值Z=∞
        2. 根据分枝法则,从尚未被洞悉节点(局部解)中选择一个节点,并在此节点的下一阶层中分为几个新的节点
        3. 计算每一个新分枝出来的节点的下限值
        4. 对每一节点进行洞悉条件测试,若节点满足以下任意一个条件,则此节点可洞悉而不再被考虑
      方法 对解空间树的搜索方式 存储结点的常用数据结构 结点存储特性 常用应用
      回溯法 深度优先搜索 堆栈 活结点的所有可行子结点被遍历后才被从栈中弹出 找出满足约束条件的所有解
      分支限界法 广度优先或最小消耗优先搜索 队列、优先队列 每个结点只有一次成为活结点的机会 找出满足约束条件的一个解或特定意义下的最优解

Tags:
0 comments



本作品采用知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议CC BY-NC-ND 4.0)进行许可。

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License (CC BY-NC-ND 4.0).