精华内容
下载资源
问答
  • 2018-07-23 08:41:26

    在之前的博客 SVM解释:二、SVM的数学基础 中,我已经大致介绍了支持向量机(SVM)的数学理论基础。从本文开始,我将逐步推导SVM是如何运用于数据分类的。由简入难,我先来介绍比较简单的,通过训练线性可分的数据分类。

    在我写的SVM的第一篇博客中,已经大致介绍了SVM是做什么的,大概是怎样一个思路,所以本文我们直接进入正题,从介绍最大边缘超平面的计算方法开始。

    1. 最大边缘超平面

    一个给定的数据集如Fig.1所示。数据集被标注为两类(黑点和白点),我们发现,此时数据集是“线性可分的”:即可以找到一个超平面,将数据集按类别分开,如图中虚线所示。当然,在二维空间内是一条线,那么在多维空间中,自然就是一个超平面了。


    不难想到,我们自然可以把这样一个超平面当做分类器。对于新的未知分类的数据点,可以根据这个点和超平面的位置关系,预测其所在分类。但是现在的问题是,这样的超平面可以有很多,我们显然应该用“最好”的那个,“最好”的定义可以这样解释:它能尽可能地区分属于不同类的数据。那你说咋样算是能尽可能区分呢,直观来说就是为现在的两类数据找一个分离超平面,使得这个平面分别与两类数据的最近的数据点之间的距离之和最大。看下面的Fig.2(a)和Fig.2(b)就明白了:Fig.2(a)中两条蓝色虚线之间的距离显然小于Fig.2(b)中两条蓝色虚线之间的距离。我们把蓝色虚线之间的距离定义为“边缘”,它就是两类数据距离分离超平面的距离之和,而分离超平面,就是与蓝色虚线平行且等距的超平面。这里,显然Fig.2(b)中红色实线是更好地分离超平面。


    下面定义几个概念:

    • 最大边缘超平面(MMH):即我上面说的“最佳”的分离超平面。它距离两类数据中最近的元组的距离之和最大,且与相应元组等距,比如Fig2.(b)中的红色实线;
    • 侧面:与MMH平行,且正好经过类1和类2数据中距离MMH最近的数据点的超平面,记为 H1,H2 H 1 , H 2 ,比如Fig2.(b)中的蓝色虚线;
    • 支持向量:在 H1 H 1 H2 H 2 上的训练元组(即数据点)被称为“支持向量”,他们离MMH一样近,比如我在Fig.2(b)中用红色标出的数据元组;

    综上所述,SVM在训练数据线性可分的情况下,要解决的问题可以用一句话概括:根据训练数据,找到最大边缘超平面(MMH).

    2. 计算过程推导

    设训练数据集为 X={X1,X2,,Xn} X = { X 1 , X 2 , … , X n } ,每个元组 Xi X i 都被标注了一个类别,类别号记为1或者-1(后面我会解释类标号的选取不影响算法,这样标只是为了方便推导)。

    假设找到的MMH的方程为:

    WX+b=0(1) (1) W X + b = 0

    其中 W={w1,w2,,wm} W = { w 1 , w 2 , … , w m } 为权重向量,其维度 m m 也是训练数据的属性数;b为标量。显然,根据这个方程,我们可以找到这两个不同类的数据元组满足的特征,即:

    • 在MMH上方的数据元组(即属于类1的数据元组),满足 WX+b0 W X + b ≥ 0
    • 在MMH下方的数据元组(即属于类-1的数据元组),满足 WX+b0 W X + b ≤ 0

    据此,我们可以接着写出侧面 H1,H2 H 1 , H 2 的方程:

    H1:WX+b=1H2:WX+b=1(2) (2) H 1 : W X + b = 1 H 2 : W X + b = − 1

    注1:解释一下 H1 H 1 H2 H 2 的方程右侧为什么要用1和-1,其实任意两个绝对值相等的正负数都是可以的。比如我们设为 k k k,等式两边同时除 k k 后,和上式就是一样的了,那能不能设置成任意两个数呢,比如2和3,也是可以的,但是你的MMH的方程就要发生变化了,所以没有这个必要,为了方便计算推导,就直接设为1和-1就行了。

    上面说过,两个类的类标号为1和-1,那根据H1 H2 H 2 的方程,对数据集中任意的元组 Xi X i 而言,下面的不等式一定成立:

    yi(WXi+b)0,yi{1,1}(3) (3) y i ( W X i + b ) ≥ 0 , y i ∈ { 1 , − 1 }

    其中 yi y i 是元组 Xi X i 的类标号,即1或-1.

    注2:解释一下我之前说的类标号的取值问题。首先名称类的类标号可以用数值来替代,比如类buy和no_buy,可以标记为1和-1;其次,数值也不一定非要取1和-1,比如你也可以取成2和3,但是这样一来,如果还要写成一个式子大于等于0这种形式,上面的不等式就要发生变化,变成

    (yi2.5)(WXi+b)0(4) (4) ( y i − 2.5 ) ( W X i + b ) ≥ 0

    所以说本质上是一样的。不管类标号怎么取,我们的目的就是要构造一个约束条件出来,而且一定是个不等式的约束条件,因为SVM的核心就是在有不等式的约束条件下解决一个凸优化无问题,这一点你慢慢看后面会明白。此外,因为两个类分别在超平面的上下两侧,对于超平面的方程而言,他们在数值上是正负相反的,所以一般情况下,我们设类标号为1和-1. 总而言之,一句话:y的取值是可以任意选两个值的,只是出于计算推导的方便和解释直观性,选取了1和-1.

    好了,现在关于超平面的方程以及数据元组和这个方程的关系我们已经列出来了,接着思考,我们说距离它的两个侧面 H1,H2 H 1 , H 2 间距最大的MMH是要求解的对象。那先来看看这个距离怎么算,我们再次列出三者的方程如下:

    H1:WX+b=1MMH:WX+b=0H2:WX+b=1(5) (5) H 1 : W X + b = 1 M M H : W X + b = 0 H 2 : W X + b = − 1

    根据计算几何的知识,我们知道 H1 H 1 和MMH的间距与 H2 H 2 和MMH的间距是相等的,都是 1W 1 ‖ W ‖ 。那现在的任务很明确了,求出使得 1W 1 ‖ W ‖ 最大的 W W 即可。

    这是典型的凸优化问题,形式化的表示如下:

    (6)max 1Ws.t. yi(WXi+b)1,i={1,2,,n}

    等价转换一下,变成:

    min 12W2s.t. 1yi(WXi+b)0,i={1,2,,n}(1) (1) min   1 2 ‖ W ‖ 2 s . t .   1 − y i ( W X i + b ) ≤ 0 , i = { 1 , 2 , … , n }

    这就是简单的将求最大值的问题转换成求最小值的问题,很好理解。至于为什么要用 12W2 1 2 ‖ W ‖ 2 ,那是为了后面的推导方便。

    OK,现在的目标函数是二次的,约束条件是线性的,它是一个凸二次规划问题。根据July的博客 支持向量机通俗导论,我们知道直接用现成的QP (Quadratic Programming) 优化包求解就行。其实到这里,关于线性可分的SVM算法就算是说完了。但是现在的问题是,如果遇到了线性不可分的情况(我将在下一篇博客中讲解),为了找到合适的分类器,我们需要将数据通过核函数映射到更高维的空间中,再寻找MMH。为了更清楚地理解核函数的相关概念,这里我们做一个转换:将公式(1)中带不等式约束的凸优化问题转换成拉格朗日对偶,通过求解拉格朗日对偶问题,计算分类器。

    3. 拉格朗日对偶的计算步骤

    关于拉格朗日对偶的预备知识我在上一篇博文 SVM解释:二、SVM的数学基础 的小节4中有详细的说明,我们已知两点:

    • 优化问题(1)可以转换成一个无约束条件的原问题 p p ∗
    • 因为满足Slater条件,原问题 p p ∗ 与对偶问题 d d ∗ 是同解的;

    这里,我们把拉格朗日对偶直接用于解决优化问题(1)。具体的求解步骤如下。

    首先,写出拉格朗日函数:

    L(W,b,α)=12W2+i=1nαi(1yi(WXi+b))(7) (7) L ( W , b , α ) = 1 2 ‖ W ‖ 2 + ∑ i = 1 n α i ( 1 − y i ( W X i + b ) )

    令原问题为:

    p=minW,bmaxαL(W,b,α)(8) (8) p ∗ = min W , b max α L ( W , b , α )

    其实这里的 W W b合起来相当于是上一篇博客4.1节中的x,我们发现这个函数是个开口朝上的抛物线,所以先计算最大值不好求解,于是进一步找到它的对偶问题:

    d=maxαminW,bL(W,b,α)(9) (9) d ∗ = max α min W , b L ( W , b , α )

    我们已知对偶问题与原问题的最优解是一样的,所以解决 d d ∗ 就是解决 p p ∗

    对偶问题 d d ∗ 本质上是无约束的最优化问题,我们先计算 minW,bL(W,b,α) min W , b L ( W , b , α ) 。固定 α α ,然后令 L(W,b,α) L ( W , b , α ) 分别对 W W b计算偏导,得到如下结果:

    L(W,b,α)W=0W=i=1nαiyiXTiL(W,b,α)b=0i=1nαiyi=0(2) (2) ∂ L ( W , b , α ) ∂ W = 0 ⇒ W = ∑ i = 1 n α i y i X i T ∂ L ( W , b , α ) ∂ b = 0 ⇒ ∑ i = 1 n α i y i = 0

    注意一下,上面这个公式(2)非常重要,后面我们要多次用到它

    将以上的结果带入 L(W,b,α) L ( W , b , α ) ,得到:

    L(W,b,α)=12i,j=1nαiαjyiyjXTiXji,j=1nαiαjyiyjXTiXjbi=1nαiyi+i=1nαj=i=1nαi12i,j=1nαiαjyiyjXTiXj(10) (10) L ( W , b , α ) = 1 2 ∑ i , j = 1 n α i α j y i y j X i T X j − ∑ i , j = 1 n α i α j y i y j X i T X j − b ∑ i = 1 n α i y i + ∑ i = 1 n α j = ∑ i = 1 n α i − 1 2 ∑ i , j = 1 n α i α j y i y j X i T X j

    那你看看,现在没有了 W W b,只有 α α ,而且问题变成了下面的带约束凸优化问题:

    max i=1nαi12i,j=1nαiαjyiyjXTiXjs.t.j=1mαiyi=0       αi0(3) (3) max   ∑ i = 1 n α i − 1 2 ∑ i , j = 1 n α i α j y i y j X i T X j s . t . ∑ j = 1 m α i y i = 0               α i ≥ 0

    注3:上面的公式(3)在后面的讲解中简称为“SVM对偶问题”,这也是SVM的核心公式。

    求解SVM对偶问题一般用SMO算法,关于SMO算法的细节我会在第5篇博客 SVM解释:五、SMO算法 中详细说明,这里暂且省略,大家知道这个问题不难求解就可以了。解出 αi α i 后,进而可以根据公式(2)得到 W W 。实验时,我们会发现αi中有很多是等于0的,只有少数是大于0的,而大于0的这些 αi α i 所对应的 Xi X i 则就是支持向量。想想为什么?因为大于0的 αi α i 对应的 Xi X i 满足:

    1yi(WXi+b)=1(11) (11) 1 − y i ( W X i + b ) = 1

    如果不满足上式的话,则无法满足KKT条件的第三项。这样,我们可以得到一个结论:大于0的 αi α i 对应的 Xi X i 就是支持向量(因为它恰好在侧面上)。而同时,那些 αi=0 α i = 0 的所对应的元组 Xi X i 则不在侧面上,他们在侧面以外,而且对于超平面没有影响。从这个角度来讲,SVM其实只与少量的支持向量有关,与其他远离超平面的大量的训练元组没有关系。所以在实际应用中,可以通过这种思想筛掉大量的训练元组,以提高效率。这也是我在第本系列第5篇博文中,讲到的求解优化问题的高效SMO算法最本质的思想。

    随后,我们可以依据这个式子求解出 b b 。从数值的稳定性上讲,建议用所有的支持向量计算b的值,并求取平均值,这样找出的 W W b合起来就是所谓的支持向量机(SVM)。

    形式化地,支持向量机(SVM)可以用下面的公式(4)表示:

    f(X)=i=1nαiyiXTiX+b(4) (4) f ( X ) = ∑ i = 1 n α i y i X i T X + b

    分类时,将测试元组 X X ∗ 带入公式(4),判断计算结果的正负性就可以预测分类了。

    好了,对于线性可分情况下的SVM的求解过程到这里就算是全部完成了。但是,这种算法只能适用于数据线性可分的情况,其实现实中用处不大,因为现实中我们遇到的数据大多时候是线性不可分的。对于线性不可分的情况处理起来会更加复杂,我将在下一篇博客中详细阐述。

    更多相关内容
  • 先来说一下为什么要看这本书,起因是最近刷LeetCode的时候,发现一个涉及到python数据结构的知识——链表,果然自己的python学习的还是有问题,所以趁此机会攻读一下算法和数据结构方面的书籍,继而有了这本书的读书...

    欢迎关注WX公众号:【程序员管小亮】

    python学习之路 - 从入门到精通到大师

    算法是一组完成任务的指令。任何代码片段都可视为算法,

    一、二分查找

    • 假设要在电话簿中找一个名字以K打头的人,可以从头开始翻页,直到进入以K打头的部分。但你很可能不这样做,而是从中间开始,因为你知道以K打头的名字在电话簿中间。

    • 假设要在字典中找一个以O打头的单词,你可以从头A开始寻找到O字母,但是你应该不会这样做,因为你知道O在什么位置——中下,所以你将从中间附近开始。

    • 假设你登录Facebook。当你这样做时,Facebook必须核实你是否有其网站的账户,因此必须在其数据库中查找你的用户名。如果你的用户名为karlmageddon,Facebook可从以A打头的部分开始查找,但更合乎逻辑的做法是从中间开始查找。

    这三种情况都是在寻找自己的目标,可以统称为查找问题。在前述所有情况下,都可使用同一种算法来解决问题,这种算法就是 二分查找

    二分查找是一种算法,其输入是一个 有序的 元素列表(必须有序的原因稍后解释)。如果要查找的元素包含在列表中,二分查找返回其位置;否则返回null。

    举一个例子,我们使用二分查找在电话簿中两个实业公司名,找到了第一个并返回了位置,没有找到第二个,所以反悔了NULL:
    在这里插入图片描述

    1)简单查找

    下面举一个例子,来说明了二分查找的工作原理。这是一个酒桌上常玩的游戏,叫做猜数字,我先随便想一个1~100的数字,然后让另一个参与者,也就是你进行猜测,目标是以最少的次数猜到这个数字。每次你猜测错误后,我都会说小了、大了或对了这样的话来给出新的范围,输的人当然要喝酒,嘿嘿。
    在这里插入图片描述
    假设你从1开始依次往上猜,猜测过程会是这样:
    在这里插入图片描述
    这是 简单查找,更准确的说法是傻找,是一种糟糕的猜数法。每次猜测都只能排除一个数字。如果我想的数字是99,你得猜99次才能猜到!真的是醉了,这样子没人和你玩了哈。

    2)更佳的查找方式

    有没有更佳的猜数法呢?当然是有的,别着急,下面接着介绍。

    从50开始猜数。
    在这里插入图片描述
    如果我说小了,这样你就知道了新的范围,也就是50 - 100,排除了一半的数字!至此,你就知道1 - 50都小了。接下来,你猜75。
    在这里插入图片描述
    如果我说大了,那余下的数字又排除了一半,也就是50 - 75!使用二分查找时,你猜测的是中间的数字,从而每次都将余下的数字排除一半。接下来,你猜63(50和75中间的数字)。
    在这里插入图片描述
    这就是二分查找,你学习的第一种算法!每次猜测排除的数字个数如下:
    在这里插入图片描述
    我们发现每一次使用二分查找时,都会排除一般的数字,简直不要太好用。换句话说,不管我心里想的是什么数字,你都能在7次之内猜到,因为每一次都能排除很多数字,当然我们说的是这个100以内猜数字是7次以内。

    假设你要在字典中查找一个单词,而该字典包含240 000个单词,你认为每种查找最多需要多少步?如果要查找的单词位于字典末尾,使用简单查找将需要240 000步。使用二分查找时,每次排除一半单词,直到最后只剩下一个单词。
    在这里插入图片描述
    因此,使用二分查找只需18步——少多了!一般而言,对于包含n个元素的列表,用二分查找最多需要 l o g 2 n log_{2}n log2n 步,而简单查找最多需要n步。

    为什么是18,难道要一次一次的数嘛?答案当然是否,使用 l o g 2 n log_{2}n log2n 进行计算,如果有的同学忘了对数,就一个例子,2的2次方是4, 2 2 = 4 2^2=4 22=4,那么 l o g 2 4 = 2 log_{2}4=2 log24=2,也就是说对数运算是幂运算的逆运算。

    二、编程实战

    如何编写执行二分查找的Python代码?这里的代码示例使用了数组。函数 binary_search 接受一个有序数组和一个元素。如果指定的元素包含在数组中,这个函数将返回其位置。我们准备跟踪的是要在其中查找目标的数组部分——最开始时为整个数组。
    在这里插入图片描述
    每一次都检查有序数组最中间的元素。
    在这里插入图片描述
    如果(low + high)不是偶数,我们就将mid向下取整。如果猜的数字小了,就相应地修改low。如果猜的数字大了,就修改high。完整的代码如下:

    python版本代码如下:

    def binary_search(list, item):
      #low and high,就是对应你要跟踪搜索的列表的哪个部分
      low = 0
      high = len(list) - 1
    
      #While 你还没有缩小到一个元素…
      while low <= high:
        # ... check the middle element
        #……检查中间元素
        mid = (low + high) // 2
        guess = list[mid]
        #找到了目标
        if guess == item:
          return mid
        #猜测的太高了
        if guess > item:
          high = mid - 1
        #猜测太低了
        else:
          low = mid + 1
    
      #目标不存在
      return None
    
    my_list = [1, 3, 5, 7, 9]
    print(binary_search(my_list, 3)) # => 1
    
    #'None' 在python中表示 0,我们用来表示找不到这个东西
    print(binary_search(my_list, -1)) # => None
    

    在这里插入图片描述
    c++版本代码如下:

    #include <iostream>
    #include <vector>
    
    using std::cout;
    using std::endl;
    
    template <typename T>
    int binary_search(const std::vector<T>& list, const int& item) {
        int low = 0;
        int high = list.size() - 1;
    
        while (low <= high) {
            int mid = (low + high) / 2;
            T guess = list[mid];
    
            if (guess == item) {
                return mid;
            }
    
            if (guess > item) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
    
        return -1;
    }
    
    // this function returns pointer to the found element rather than array index
    template <typename T>
    const T* binary_search2(const std::vector<T>& list, const T& item) {
        const T* low = &list.front();
        const T* high = &list.back();
    
        while (low <= high) {
            // "guess" is the element in the middle between "high" and "low"
            const T* guess = low + ((high - low) / 2);
    
            if (*guess == item) 
                return guess;
            
            if (*guess > item) {
                high = guess - 1;
            } else {
                low = guess + 1;
            }
        }
    
        return nullptr;
    }
    
    int main() {
        std::vector<int> my_list = {1, 3, 5, 7, 9};
        const int* binary_search2_result = binary_search2(my_list, 9);
        const int* binary_search2_null = binary_search2(my_list, 4); // test finding element that is not in the list
    
        cout << "Binary search for number 3: " << binary_search(my_list, 3) << endl;
        cout << "Binary search 2 for number 9 (memory address): " << binary_search2_result << endl;
        cout << "Binary search 2 for number 9 (value): " << *binary_search2_result << endl;
        
        if (binary_search2_null == nullptr) {
    		cout << "4 was not found in the list" << endl;
    	}
    
        return 0;
    }
    
    

    如果想要使用二分查找在一个包含128个名字的有序列表中查找一个名字,请问最多需要几步才能找到?

    import math
    
    int(math.log(128, 2))  # 或者int(math.log2(128))
    

    在这里插入图片描述

    三、运行时间

    每次介绍算法时,都要将讨论其运行时间。一般而言,应选择效率最高的算法,以最大限度地减少运行时间或占用空间。

    回到前面的二分查找。使用它可节省多少时间呢?简单查找逐个地检查数字,如果列表包含100个数字,最多需要猜100次。如果列表包含40亿个数字,最多需要猜40亿次。换言之,最多需要猜测的次数与列表长度相同,这被称为 线性时间(linear time)

    二分查找则不同。如果列表包含100个元素,最多要猜7次;如果列表包含40亿个数字,最多需猜32次。厉害吧?二分查找的运行时间为 对数时间(或log时间)

    下表总结了我们发现的情况。
    在这里插入图片描述
    可以发现两个算法的时间成本上的差别。

    四、大O 表示法

    1)算法运行时间以不同的速度增加

    下面来举一个高大上的例子,火箭登录月球计算着陆点,你回看到两种算法的运行时间呈现不同的增速。

    Bob需要做出决定,是使用简单查找还是二分查找。使用的算法必须快速而准确。

    • 一方面,二分查找的速度更快。Bob必须在10秒钟内找出着陆地点,否则火箭将偏离方向。
    • 另一方面,简单查找算法编写起来更容易,因此出现bug的可能性更小。Bob可不希望引导火箭着陆的代码中有bug!

    为确保万无一失,Bob决定计算两种算法在列表包含100个元素的情况下需要的时间。假设检查一个元素需要1毫秒。使用简单查找时,Bob必须检查100个元素,因此需要100毫秒才能查找完毕。而使用二分查找时,只需检查7个元素(log2100大约为7),因此需要7毫秒就能查找完毕。然而,真的是这个时间嘛?实际要查找的列表可能包含10亿个元素,在这种情况下,简单查找需要多长时间呢?二分查找又需要多长时间呢?
    在这里插入图片描述
    Bob使用包含10亿个元素的列表运行二分查找,运行时间为30毫秒(log21 000 000 000大约为30)。他心里想,二分查找的速度大约为简单查找的15倍,因为列表包含100个元素时,简单查找需要100毫秒,而二分查找需要7毫秒。因此,列表包含10亿个元素时,简单查找需要30 × 15 = 450毫秒,完全符合在10秒内查找完毕的要求。Bob决定使用简单查找。这是正确的选择吗?

    不是,当然不是。实际上,Bob错了,而且错得离谱。列表包含10亿个元素时,简单查找需要10亿毫秒,相当于11天!为什么会这样呢?因为二分查找和简单查找的运行时间的增速不同,就是物理上常说的加速度。
    在这里插入图片描述
    看到了吗?运行时间的增速有着天壤之别。

    简单来说,就是随着元素数量的增加,二分查找需要的额外时间并不多,而简单查找需要的额外时间却很多。因此,随着列表的增长,二分查找的速度比简单查找快得多。Bob以为二分查找速度为简单查找的15倍,这不对:列表包含10亿个元素时,为3300万倍。有鉴于此,仅知道算法需要多长时间才能运行完毕还不够,还需知道运行时间如何随列表增长而增加。这正是 大O表示法 的用武之地。

    大O表示法指出了算法有多快。例如,假设列表包含n个元素。简单查找需要检查每个元素,因此需要执行n次操作。使用大O表示法,这个运行时间为O(n)。单位秒呢?没有——大O表示法指的并非以秒为单位的速度。大O表示法让你能够比较操作数,它指出了算法运行时间的增速。

    再来看一个例子。为检查长度为n的列表,二分查找需要执行log n次操作。使用大O表示法,这个运行时间怎么表示呢?O(log n)。一般而言,大O表示法像下面这样:
    在这里插入图片描述
    这指出了算法需要执行的操作数。之所以称为大O表示法,是因为操作数前有个大O。

    2)理解不同的大 O 运行时间

    下面来看一些例子,看看你能否确定这些算法的运行时间。首先拿出纸和笔,画一个网格,它包含16个格子。
    在这里插入图片描述
    如果想要绘制这样的网络,有什么好的算法嘛?

    • 算法1

    一种方法是以每次画一个的方式画16个格子。记住,大O表示法计算的是操作数。在这个示例中,画一个格子是一次操作,需要画16个格子。如果每次画一个格子,需要执行多少次操作呢?
    在这里插入图片描述
    这应该是不难的,画16个格子需要16步。这种算法的运行时间是多少?暂时不知道。

    • 算法2

    请尝试这种算法——将纸折起来。在这个算法中,将纸对折一次就是一次操作。第一次对折相当于画了两个格子!再折,再折,再折。
    在这里插入图片描述
    折4次后再打开,便得到了漂亮的网格!每折一次,格子数就翻倍,折4次就能得到16个格子!
    在这里插入图片描述
    感受到了嘛?有一种二分寻找的感觉。每折一次,绘制出的格子数都翻倍,因此4步就能“绘制”出16个格子。这种算法的运行时间是多少呢?

    答案如下:算法1的运行时间为O(n),算法2的运行时间为O(log n)。

    3)大O 表示法指出了最糟情况下的运行时间

    假设使用 简单查找 在电话簿中找人。因为简单查找的运行时间为O(n),这意味着在最糟情况下,必须查看电话簿中的每个条目。如果要查找的是Adit——电话簿中的第一个人,一次就能找到,无需查看每个条目。考虑到一次就找到了Adit,请问这种算法的运行时间是O(n)还是O(1)呢?

    当然还是O(n),简单查找的运行时间总是为O(n)。至于上面的情况,在查找Adit时,一次就找到了,这是最佳的情形,但大O表示法说的是 最糟的情形。因此可以说,在最糟情况下,必须查看电话簿中的每个条目,对应的运行时间为O(n)。这是一个保证——简单查找的运行时间不可能超过O(n)。

    最简单地说,就是最大值,是个上限,实际上每一种可能都有,但是在比较讨论时,就是使用最糟糕的情况。

    4)一些常见的大O 运行时间

    下面按从快到慢的顺序列出了你经常会遇到的5种大O运行时间。

    • O(log n),也叫 对数时间,这样的算法包括二分查找。
    • O(n),也叫 线性时间,这样的算法包括简单查找。
    • O(n * log n),这样的算法包括第4章将介绍的 快速排序——一种速度较快的排序算法。
    • O(n2),这样的算法包括第2章将介绍的 选择排序——一种速度较慢的排序算法。
    • O(n!),这样的算法包括接下来将介绍的 旅行商问题 的解决方案——一种非常慢的算法。

    想象一下他们的函数图像
    在这里插入图片描述
    还有其他的运行时间,但这5种是最常见的。这里做了简化,实际上,并不能如此干净利索地将大O运行时间转换为操作数,但就目前而言,这种准确度足够了。可以获得的主要启示如下:

    • 算法的速度指的并非 时间,而是 操作数的增速
    • 谈论算法的速度时,说的是随着输入的增加,其运行时间将以什么样的速度 增加
    • 算法的运行时间用 大O表示法 表示。
    • O(log n)比O(n)快,当需要搜索的元素越多时,前者比后者快得越多。

    5)旅行商问题

    阅读前一节时,你可能认为根本就没有运行时间为O(n!)的算法。然而并不是,这节介绍的就是一个运行时间极长的算法。这个算法要解决的是计算机科学领域非常著名的旅行商问题,其计算时间增加得非常快。

    问题如下:

    有一位旅行商。他需要前往5个城市。
    在这里插入图片描述
    这位旅行商要前往这5个城市,同时要确保旅程最短。为此,可考虑前往这些城市的各种可能顺序。
    在这里插入图片描述
    对于每种顺序,都计算总旅程,再挑选出旅程最短的路线。5个城市有120(5!)种不同的排列方式。因此,在涉及5个城市时,解决这个问题需要执行120次操作。涉及6个城市时,需要执行720(6!)次操作(有720种不同的排列方式)。涉及7个城市时,需要执行5040(7!)次操作!

    推而广之,涉及n个城市时,需要执行n!(n的阶乘)次操作才能计算出结果。因此运行时间为O(n!),即阶乘时间。除非涉及的城市数很少,否则需要执行非常多的操作。如果涉及的城市数超过100,根本就不能在合理的时间内计算出结果——等你计算出结果,太阳都没了。

    这种算法很糟糕!可是别无选择。。。这是计算机科学领域待解的问题之一。

    五、总结

    • 二分查找的速度比简单查找快得多。
    • O(log n)比O(n)快。需要搜索的元素越多,前者比后者就快得越多。
    • 算法运行时间并不以秒为单位。
    • 算法运行时间是从其增速的角度度量的。
    • 算法运行时间用大O表示法表示。

    参考文章

    • 《算法图解》
    展开全文
  • 插入排序算法介绍 算法逻辑 伪代码 复杂度

    算法设计策略

    算法中的基本设计策略包括:蛮力法、分治法、减治法、变治法、时空权衡等。本专题将一一介绍这些设计策略在一些重要问题中的应用,包括排序、查找、图问题、组合问题。本文首先介绍蛮力法和减治法的应用。

    蛮力法

    使用蛮力法的意义在于:首先这种解法一般体现了解决问题最直接的思路,几乎对于任何问题都适用(越简单越普适);其次,在问题规模不大的时候,没有必要使用高技巧性的方法,反而耗费更多代价。并且在某些基本问题,如求数组和,求列表最大元素等,蛮力法已经是一种高效的方法。
    考虑蛮力法在排序问题中的应用。一种蛮力法的方法是选择排序。每次扫描整个列表,通过逐个比较,找到最小的元素(每次更新最小的元素,最后得到的即是整个序列中的最小元素),再把每次找到的最小元素和序列中的首位元素交换(不另外放一个序列,因为原地排序节省空间)。这样,为了排出有序列,需要比较 n ( n − 1 ) 2 \frac{n(n-1)}{2} 2n(n1)次,也就是说,其时间复杂度为 O ( n 2 ) O(n^2) O(n2)

    减治法

    减治法思想

    减治法利用了这样一种关系:原问题的解和一个同样问题但规模较小的问题的解之间的关系。这样的表述本质上采用了递归思想,但从具体的解法层面,可以用递归求解,也可以用非递归的方法求解。本文要讲述的两种方法,一种就采用了非递归,另一种用了递归。减治法可以分为3种:

    1. 问题规模减去一个常量:规模为n的问题的解 ↔ \leftrightarrow 规模为n-1问题的解,例:插入排序、深优和广优
    2. 问题规模减去常数因子:规模为n问题的解 ↔ \leftrightarrow 规模为 n a ( a > 1 ) \frac{n}{a}(a>1) an(a>1),例:折半查找
    3. 问题规模减去可变因子:每次迭代时,规模减小的模式和其他次迭代时可以不同,例:选择问题(找顺序统计量)

    本文先讨论减一技术。另几种方法在本专题后续文章中会讨论到。

    算法设计中的递推类型

    上面的文字表述看起来不是很清晰,特别是其没有清楚的表现出减治法和分治法的区别和联系。下面,我们用递归表达式对几种常见的、用递归表述的算法设计思路进行更清晰的表述。
    减一法
    由于每次的子问题就是原问题的规模减1,并且对于一个规模为n的问题的求解时间,除了包括求解规模n-1的问题,还包括对规模为n的问题化简到规模n-1问题的时间,以及对规模n-1问题扩展为规模n问题的时间,后两者的时间可以合并为一个式子,因此可以得到递归式:
    T ( n ) = T ( n − 1 ) + f ( n ) T(n)=T(n-1)+f(n) T(n)=T(n1)+f(n)
    减常数因子
    这种情况下,每次的子问题是原问题的规模的 n b \frac{n}{b} bn,很多情况下,b为2(如折半查找,每次是和有序数组中间元素进行比较)
    T ( n ) = T ( n b ) + f ( n ) T(n)=T(\frac{n}{b})+f(n) T(n)=T(bn)+f(n)

    减可变因子
    这种情况下,无法用递归表达式表示出来。因为每次的子问题规模取决于上一步进行的情况,而不完全取决于上一步的问题规模。如,在选择问题中,查找某个顺序统计量,对每个子问题先找中轴,再用快速排序的分区过程(两个方向相反的扫描)排出中轴两侧元素,通过此时中轴元素位置决定下一次分区的区域,亦即决定了下一个子问题的规模。

    分治法
    分治法的核心在于将一个问题分成若干个规模相同的子问题,每个子问题再继续分解,直到分解出可以常数时间求解的子问题,再从底向上逐层求解子问题,并对子问题解进行合并。可以看出,其与减治法最大的差别在于,每次分解出的子问题不是一个,而是多个。因此,个人理解,减治法可以看成是分治法的一种特例。分治法的递归式为:
    T ( n ) = a T ( n b ) + f ( n ) T(n)=aT(\frac{n}{b})+f(n) T(n)=aT(bn)+f(n)

    减一法应用之一:插入排序

    算法思想

    插入排序法可以类比扑克牌抓牌时候的排序过程。每新抓一张牌,会把这张牌和已有的牌比较大小,依此选择插入点。因此,每次抓牌之前,手中的牌都是一个排好序的序列。归结到算法上,是:在每次排序之前,数组A中已经有部分已经排好序的子数组B。每次要做的是取一个剩下子数组C的数,将其与B中数比较,选一个合适的位置插入。
    在C对B中元素的查找并插入中,实际上有多种实现方法。假设我们要将数组从左到右排成从小到大。一种是从左到右扫描B中元素,查到B中第一个大于等于 C j C_j Cj的元素即进行插入操作。一种是从右到左扫描,查到B中第一个小于等于 C j C_j Cj的元素即进行插入。还有一种做法是折半查找。三种情况的效率上界都相同,这里只讨论从右到左扫描的查找情况。
    可以发现,对这一排序方法的表述本质上基于递归思想。也就是可以基于从顶到底的递归函数调用实现算法。但对于这一问题,从底到顶的非递归方法效率会更高。

    过程

    可以分析这一过程的具体步骤:先在序列 A A A抽出第2个元素 a 2 a_2 a2,将其与 a 1 a_1 a1比较大小,若 a 2 < a 1 a_2<a_1 a2<a1,将 a 2 a_2 a2放在 a 1 a_1 a1左侧,若 a 2 > a 1 a_2>a_1 a2>a1,将 a 2 a_2 a2放在 a 1 a_1 a1右侧。这样,在 A A A中排好了两个元素的有序子列 ( a 1 ′ , a 2 ′ ) (a_1^{'},a_2^{'}) (a1,a2)本次排序结束再抽出 a 3 a_3 a3,将其与 a 2 ′ a_2^{'} a2比较,若大于,令 a 3 ′ = a 3 a_3^{'}=a_3 a3=a3,其他元素均不变,本次排序结束。若小于,先令 a 3 ′ = a 2 ′ a_3^{'}=a_2^{'} a3=a2再将 a 3 a_3 a3 a 1 ′ a_1^{'} a1比较。若大于,令 a 2 ′ = a 3 a_2^{'}=a_3 a2=a3本次排序结束。若小于 a 1 ′ a_1^{'} a1,因为 a 1 ′ a_1^{'} a1左边没有其他数了, a 3 a_3 a3只能放在 a 1 ′ a_1^{'} a1左边,也就是令 a 2 ′ = a 1 ′ a_2^{'}=a_1^{'} a2=a1 a 1 ′ = a 3 a_1^{'}=a_3 a1=a3本次排序结束。由特例可以发现,整个排序过程有两次循环。大循环是从序列A中依此抽元素 a k a_k ak,小循环是将 a k a_k ak A ′ A^{'} A中每个元素比较。小循环中止条件是 a k > a j ′ a_k>a_j^{'} ak>aj a k a_k ak插到 a j ′ a_j^{'} aj右侧, a j + 1 ′ a_{j+1}^{'} aj+1左侧),或是 j − 1 = 0 j-1=0 j1=0 a k a_k ak插到序列最左侧),循环继续条件则反过来。
    据此,可以写出该过程的代码。

    代码

    伪代码

    for j=2 to len(A)
    //为了避免在赋值的过程中数字丢失,需要另设一个参数存放每次要插入的元素。且注意循环从2开始,因为每次循环涉及和前一数的比较,第一个数没有前一个数。
      key = a[j]
      //减一法思想:每次要对j排序之前,前提是其之前的数已经排好序。
      //每次都是先和序列中前一个数比大小。这里的a[i]相当于A'序列中的数。
      i = j-1
      //小循环。这里用while书写,因为循环次数未知。根据本文第一部分的分析,可写出循环继续条件
      while key < a[i] & i>0
      //待排序元素值小于A'第i个值,则A’第i个值往后移一位,即A'中第i+1个元素被赋值为原第i个元素的值。注意待排序元素的原index不用动,可以认为是一个虚值,只在最终确定好位置之后再插进去。
          a[i+1]=a[i]
          //本方法是往A'的左侧扫描,故要规定减1的步长
          i=i-1
          //若新元素大于等于A'第i个值,则将该元素插到A'第i+1个位置,同时循环结束。新元素右侧的元素位置都已经更新过,左侧的则不用变。
          //若新元素小于A'所有值,即扫描到了i=0,则循环结束,该元素插到A’第1个位置,也即i+1。故两种情况可以统一表示。
      a[i+1]=key
        //一个新元素的插入完成。从原序列中抽下一个元素(转到j的大循环)。
    

    python代码
    首先构造一个实例:对序列A=[1,4,6,3,5,10,7,3,8]从小到大排序。
    当然,用python内置的sorted函数可以一次性完成排序:

    sorted(A, reverse=FALSE)
    

    也可以根据上述伪代码自己编一个sorted函数:

    //升序排列
    def sort(lista):
        for j in range(1,len(lista)):
            key = lista[j]
            i = j-1
            while key > lista[i]  and i>=0:
                lista[i+1]=lista[i]
                i = i-1
            lista[i+1]=key
            print(lista)
    sort(A)
    
    //降序排列只要把key > lista[i]换成key<lista[i]即可
    

    算法效率

    这里讨论该算法的运行时间。估计运行时间一般要用RAM模型。该模型假定:1、语句只能是真实的基本计算机指令,而不能是一个封装好的包。2、每一语句的执行时间是一个常量。3、不同语句不能并行计算。
    虽然这些条件不一定成立(如现在流行的并行计算),但在分析算法时间复杂度中有很大作用。
    下图是插入排序算法每一步的执行时间与执行次数统计(图源自《算法导论》)。

    在这里插入图片描述

    为何第一句运行次数为n而非n-1?需要注意for,while循环语句执行测试次数比执行循环体次数多1。
    t j t_j tj指第j个元素进行插入时,进行while循环测试的次数(注意比循环体执行次数多1)。循环体执行次数即待插入元素与A‘序列元素比较的次数,取决于是序列排序程度。最好情况是完全升序,这样即不用执行循环体, t j = 1 t_j=1 tj=1。最坏情况是完全降序,这样待插入元素需要和j之前的j-1个元素比较,则有 t j = j t_j=j tj=j。可以总结出技巧:同一级循环体内的语句执行次数应当是相同的。while下面的语句实际是和for循环一级的,因此执行次数也是n-1。
    根据RAM的假设,若要知道该算法耗费总时间,求这些步的时间次数乘积和即可。
    计算可得,在最好情况下, T ( n ) = a n + b T(n)=an+b T(n)=an+b
    最坏情况下, T ( n ) ≈ n ( n − 1 ) 2 T(n)\approx\frac{n(n-1)}{2} T(n)2n(n1)
    平均情况下, T ( n ) ≈ n 2 4 T(n) \approx\frac{n^2}{4} T(n)4n2
    因此,该算法时间效率的渐进上界是 O ( n 2 ) O(n^2) O(n2)。同时,注意到该算法是原地排序,需要的额外空间仅为常数。

    减一法应用之二:深优和广优查找

    算法思想

    对象:拓扑结构

    拓扑结构是一种重要的数据结构,其基本组成为节点和节点之间的连线。在很多实际问题的解决中,通过构造拓扑图的数据结构往往可以高效的解决问题。比如,在线程的调度问题中,每个线程具有优先级,时常需要根据优先级进行查找、删除、添加等操作,这时,构造一个堆的数据结构,进行堆的构造、删除、排序等操作可以对这些问题进行很好的解决。而堆本质就是一颗完全二叉树,也就是一个拓扑结构。又比如,在旅行商问题中,我们希望在n个城市中找到一条从某个城市出发,经过所有城市并回到出发地的最短路径,虽然我们可以用蛮力法,将所有的排列组合都写出来,但一种更高效的办法是从某个点出发,对所做的选择构造一颗状态空间树。如果构造树的过程中不考虑任何简化方法,最后树的叶结点就是所有可能排列组合的结果。但我们在构造过程中可以做一系列简化,如直接抛弃不可能的选择所在节点及其子树,也就是进行剪枝,最后找到解的时候,我们可能只需要得到一棵较简单的状态空间树。这就是回溯法分支定界法的核心思想,在之后的专题中会作更多说明。

    拓扑结构可以用图G=(V,E)表示,其存储一般有邻接链表和邻接矩阵两种方式。不同的存储方式一般会导致相同算法的效率不同。对于图G的邻接链表,其长度之和为O(E),因此存储空间需求为节点数+链表长度=O(V+E)。G的邻接矩阵存储空间需求为 O ( V 2 ) O(V^2) O(V2)

    BFS & DFS

    在处理拓扑结构的算法中,经常会用到广度优先(BFS)和深度优先搜索(DFS)作为基本思路。这两种算法看似只是对一个拓扑结构进行遍历,但将其巧妙使用可以解决很多困难问题。比如,在前面所述旅行商问题中,可以把城市抽象成节点,路径及其距离抽象为连线,构造空间状态树的过程实际上就涉及对节点的遍历,在无约束条件下按照某种规则可以不遗漏的遍历所有节点,在有约束条件下也就一定不会遗漏(顶多是有意舍去某些节点),因此也就有可能找到全局最优解。因此,我们需要用DFS/BFS的思路构造一棵状态空间树。DFS和BFS在图算法中的应用在本专题之后的文章中会详细阐述。本文先介绍这两种算法本身。

    广度优先搜索(BFS) 的基本思想是,从某个节点出发,先找出所有与其直接可达的节点,再对这些子节点分别找出所有与他们直接可达的节点,再重复上述过程。这样,搜索到的区域即像一个同心圆一样往外逐层往外扩张,直到一个节点无法找到未遍历过且直接可达的节点为止。再检查该过程有没有把所有的节点遍历完,如果没有,则用其他节点再进行一次这个过程。

    深度优先搜索(DFS) 的基本思想是:从某个节点s出发,先任意找出一个与其直接可达的节点,再从该子节点出发,重复上述过程,直到不再有未遍历过且直接可达的节点。此时,后退到最后一个节点的母节点,从在这里出发,找到另一个之前未遍历过且直接可达的节点,重复上述过程,直到从源节点s也找不到未访问过的节点,则这时,源节点s的所有连通分量的所有顶点都被遍历过。

    过程

    广搜
    为了跟踪算法的进展,广优和深优把节点在概念上涂上黑、白、灰色,以表示节点本身和其邻接节点的发现情况,因为根据上面描述可以发现,两种搜索探索的方向就是根据节点的发现情况。

    灰色节点表示该节点第一次被发现,且尚未从该节点扫描其邻接点。白色节点表示该节点未被发现。黑色节点表示该节点被发现,且该节点的邻接节点已全部遍历,没有未被发现的邻接节点。

    在广优搜索过程中,会形成一棵广度优先树,所谓广度优先树,就是一个描述节点被发现过程的树结构,其根节点即为搜索开始时的源节点s。广优树一个重要的性质就是可以确定最短路径。到达每个节点时经历的边数 d d d 即为源节点到该节点的最短路径。这个结论是由严谨的证明推导出来的,但从直观上也比较容易理解,关键要抓住这个结论成立的前提条件:图中各边的权重都是1,因此,使用广优时,由于该算法是一层层往外推,外层的路径数一定大于里层路径数。设节点u到s的最短路径为k,则u的邻接且未遍历节点一定是其外面一层节点,故其最短路径一定是k+1,若其最短路径小于等于k,则一定已经遍历过。

    下面举例说明广优搜索的过程。下图就是一个广度优先树的生成过程。这个树和我们平常看见的从顶往下画的形式不太一样,改画成从顶往下的典型树形式,会损失一些连线的信息,但看节点遍历的先后次序可能会更清晰。这里,加粗的边是被BFS发现的边,黑色的点是被BFS发现的点。从图I可以看出,BFS可以发现所有点,但未必能发现所有的边。实际上,BFS只能发现从源节点s到图中任一点的某条最短路径,非最短路径发现不了;最短路径的所有可能也无法全部发现。


    首先有个初始化的过程,将图中所有节点涂成白色。(a)中,开始搜索时,以s为源节点,第一次被发现,从白色成为灰色。(b)中,从s探索其邻接点,发现了r和l,则r和l由白转灰,s由灰转黑。再任从r,w中取一个继续搜索,取哪个会影响广度优先树的结构,但不会影响树的深度(可以自己按照节点探索的顺序画一个从顶向下的树形式,看同层节点改变探索顺序对树的影响)。(c )中从w继续探索其所有邻接点,发现了t和x,则w转黑,t,x转灰。这样重复下去。再讲一下(f)步之后。可以看到,此时,广优树中已经没有白色节点。此时从灰色节点u搜索所有邻接点,只能发现灰色或黑色的节点,说明其邻接点都遍历过了,因此也变黑。y也是同样的情况。

    但不要忘记,我们进行广优搜索的目的是要遍历这个图中的节点,也就是我们要按一定顺序输出我们遍历过的所有节点。我们可以构造一个容器用来存储遍历的元素,每次从容器出来一个即输出一个元素。对于BFS来说,可以发现,先访问的节点也最先被涂黑(结束访问),因此,令这个容器保证元素从容器中出来的顺序即是其被访问的顺序会比较容易。很自然的联想到,队列即满足这种先进先出的要求。因此,我们可以构造一个队列,跟踪每个元素被访问的情况。队列初始为空,结束时也为空。
    构造队列的另一个原因是我们在这里没有调用递归函数。通过队列,定义循环的起始,我们即可以实现从底到顶的迭代。若我们构造一个灰色节点队列,则用该队列还可以定义搜索的方向,即从哪个点开始搜索邻接点。我们可以从灰色节点队列的首位元素开始搜索,搜索时让其出队,并涂黑。也就是说,我们构造队列的目的之一就是让图中每个元素都能逐个出队,即输出。

    深搜
    深度优先搜索在算法上的处理方式和广优类似,如节点的颜色及其对应概念。但节点的属性有所区别。深优中的节点不再定义经过路径长度这个属性d,而是定义第一次发现节点u(u涂成灰色)的时间点 u.d 和完成对u的邻接链表搜索(u涂成黑色)的时间点 u.f 。
    以下举例说明DFS的搜索过程。

    代码

    广搜
    下面给出伪代码。广搜在表述上仍然是递归的形式,即搜索到子节点的前提是搜索到了其前驱节点。但本代码中没有采用递归函数调用的形式,因此我们需要进行循环迭代,也就需要规定循环何时开始、结束、循环方向、循环体。注意到,在BFS中,先访问的节点也最先被涂黑(结束访问),很自然的联想到,队列即满足这种先进先出的要求。因此,我们可以构造一个灰色节点队列。循环开始时队列为空;结束时队列也为空。该队列还可以确定循环方向:从灰色节点队列的首位元素开始搜索,搜索时让其出队,并涂黑。循环体便是队列中的每个元素。

    代码中,G表示输入的图,s表示源节点,u,v均表示图中的某个节点,V表示图中的节点集合,v.d表示到达节点v时经历的边数,v.π表示节点v的前驱节点,即是从哪个点直接访问它的,v.color表示v节点颜色。定义π是为了确定访问路径,v的所有前驱节点构成的路径即为从源节点s到v的最短路径(也是路径上任一点访问v的最短路径)。对应到上面的图,实际上,只有u成为v的前驱顶点(u = v.π),u和v之间的边才能被访问到,也就是被涂黑,而并非只要u和v相邻,连接二者的边就一定能被发现。

    BFS(G,s)    
    1 for each u in G.V-{s}:
    2  u.color = white    ##初始化,对源节点以外的各属性赋值
    3  u.d = ∞
    4  u.π = Nil
    5  s.color = gray   ##对源节点各属性赋值
    6  s.d = 0
    7  s.π = Nil
    8  Q = ∅        ##构造队列。此处以灰色节点为例。实际上,因为所有节点都要经历白-灰-黑,因此构造不同颜色节点的队列没有区别
    9  ENQUEUE(Q,s)     ##源节点s入队
    10 While Q ≠ ∅:       ##此处即开始搜索节点的循环,知道储存灰色节点的集合成为空集,则此时图中所有节点颜色均为黑色。
    11   u = DEQUEUE(Q)     ##11步以后的逻辑解释见下面正文部分
    12   for each v in Adj(u):
    13     if v.color == white:
    14       v.color = gray     ##新发现的节点,属性相应赋值
    15       v.d = u.d+1
    16       v.π = u
    17       ENEQUEUE(Q,v)     ##将该灰色节点入队
    18   u.color = black     #出队的元素涂黑
    

    代码中,11步之后的逻辑较难理解。首先,不管u的邻接点是什么颜色,灰色节点都要涂黑出队,因为灰色节点表示的一定是访问过的元素。但不能让灰色节点一次性都出队,因为需要对每个灰色节点的邻接点逐个访问一遍。因此,需要挨个出队,每个元素出队的时候访问一遍其邻接点。如果u的邻接点v中有白色,则v要涂成灰色。再将该灰色节点入队,并进行灰色节点队列中首位元素出队、搜索邻接点的循环。若v非白色,即都是发现过的元素,就不要动v了。因为:若v是黑,已经出队,不需再操作。若v是灰,则肯定在某时会出队(11步)并涂黑(18步),也就不需在12-17步的循环中对其操作。
    也就是说,11-18步实际可以拆成两个部分:让灰色节点出队并变黑(11,18)以及确定灰色节点并将其入队(12-17)。
    可以发现,虽然广优的解决思路本质使用了递归的思想,即为了访问v所在的一层,我们需要访问完上一层所有节点(变灰或黑),因此,可以用自顶向下递归调用函数的形式写算法,但这里用了效率更高的自底向上循环迭代的方式设计算法。

    深搜
    这里的代码进行了递归调用函数。深搜的递归表述是,为了扫描完u的邻接链表使u变黑,我们需要先扫描完u邻接点的所有邻接链表。
    那么,如果不用递归调用函数,我们能否仿照广优,构造一个循环体,使用迭代写出代码呢?深优的特点是,发现u越早,结束对其邻接链表搜索的时间越晚,因为发现u之后不是对其邻接点一次性扫描,而是对邻接点中的一个往下探索,每次只探索一个邻接点,再自底往上补充那些没访问到的邻接点,因此最后才能把u的邻接点都访问完。这样就形成了一个典型的先进后出的模式,因此,我们可以用栈作为循环体,最先发现的元素最后出栈,最晚发现的元素最早出栈。

    DFS(G,s)    
    1 for each u in G.V:   ##初始化,对源节点以外的各属性赋值,同时定义一个全局变量time,用来确定每个节点的访问开始和结束时间d,f
    2  u.color = white    
    3  u.π = Nil
    4  time = 0
    5 for each u in G.V:
    6   if u.color ==  White:
    7     DFS-VISiT(G,u)
    
    DFS-VISiT(G,u)     
    1  time = time +1    
    2  u.d = time          ##源节点的d为1。后面每调用一次DFS-VISIT即表示新发现了一个节点,而由于深搜中,节点u发现时间=从节点u开始访问下一个节点的时间,因此每次调用该函数,对应参数中节点的发现时间都要+1
    3  u.color = Gray 
    4  for each v in Adj(u) :
    5    if v.color == white:
    6      v.π = u          ##新发现的节点,属性相应赋值
    7      DFS-VISIT(G,v)   
    8  u.color = black   ##当在u的邻接点中已经找不到白色节点了,说明u的邻接表已经全部搜完,则u变成黑色,且其结束时间为发现时间+1
    9  u.f = time+1
    

    算法效率

    从BFS的过程可以看出,要完成搜索,首先进行初始化,复杂度O(V)。然后伪代码的11-18步,即是逐层扫描每个点v的邻接链表Adj[v],每个点的邻接链表扫了一遍搜索即结束。加和,即需要执行 ∑ v ∈ V A d j [ v ] \sum_{v\in V}Adj[v] vVAdj[v] 次。这个数字大小和数据存储格式有关。若以邻接链表的形式存储,上文中说到图G的邻接链表长度之和为O(E),则需执行O(E)次,故DFS过程总的复杂度为O(V+E)。对于邻接矩阵形式存储的数据,复杂度即为 O ( V 2 ) O(V^2) O(V2)
    从DFS过程的伪代码中可以看出,第1-4行的for循环执行V次,复杂度为O(V)。第5行的for循环含义是对每个节点v调用1次DFS-VISIT,所以我们需要看每个v的DFS-VISIT时间,并在V上加总,即能得到DFS的5-7行总运行时间。而对于每个节点v的DFS-VISIT调用,复杂度只要看循环的次数。每次需要对邻接表中的所有元素执行一次for循环,即需要Adj[v]次。和上述讨论类似,则DFS过程总的复杂度为O(V+E)。对于邻接矩阵形式存储的数据,复杂度 O ( V 2 ) O(V^2) O(V2)

    附:算法效率度量详解

    算法效率是比较不同算法优劣的重要指标。因此,我们需要知道如何衡量算法效率。算法效率分为时间和空间效率。时间效率指算法运行时间;空间效率指算法需要的额外空间(除了输入规模之外)。虽然传统教材讨论算法时间效率更多,但在大数据的情况下(如1PB以上的数据),空间效率的影响也许同样重要。这里还是主要讨论时间效率的衡量,空间效率衡量的逻辑和其基本一致。
    直观的思考是,一般算法的运行时间和这些因素有关:输入规模、特定输入的细节,以及算法实现思路的不同。下面对这三个因素一一讨论。

    输入规模
    一般在算法分析中,我们会假定输入规模为无穷大,为了看运行时间随着输入规模增长的变化情况。因为当规模较小时,实际上不同算法的时间效率之间差别不会很大,比较起来意义不大。也因为这种特性,在算法运行时间是一个多项式,我们一般只会看有最高次数的项,或者说是增长速度更快的项。
    对于某个特定的实例,在选择算法时,输入规模不是唯一的考虑因素。代码的紧凑性、简洁性、运行时间表达式中低阶项的系数都是可以考虑的因素。如,虽然快排是基于比较的排序算法中渐进效率最优的,但当输入规模较小时,完全可以使用插入排序等虽然在渐进效率上非最优但代码紧凑的算法,速度甚至可能更快。即使是选择排序这种蛮力算法,由于代码的简单性,使用也未为不可。

    特定输入的细节
    对于同一种算法、同样的输入规模,特定的输入情况决定了其运行时间效率存在不同情况,因此在非正式的讨论中,我们一般将算法的效率划分为三种:最差、最好和平均效率。最差情况效率的分析往往更重要,因为:1、最差情况确定了算法运行时间的下界,如果可以证明A算法的最坏情况都比B算法的最好情况快,那A在时间效率上一定是优于B算法的。2、大多数情况下,平均情况和最坏情况一样坏。如在插入排序中,平均情况是有一半数是升序排好的, t j = j / 2 t_j=j/2 tj=j/2,这样算出的T(n)仍然有二次项。当然,也存在例外,即平均情况和最好情况差别不大,时间效率在一个数量级上,如快速排序。并且,在随机算法中,可以通过对输入的分布作一个随机化从而得到使我们可以更简单的分析平均情况运行时间。当然,作为一个严谨的分析,我们一般要把三种情况都讨论到。

    算法实现思路
    实际上,对于同一个算法的思路,其实现方法的不同也决定了其效率。比如在本文的插入排序中,都是基于减一法的思想。但在具体的实现上,可以采用递归或非递归;在元素查找的方法上,可以采用逐个扫描或者二分查找。使用不同的实现方法,即使效率的渐进上界可能相同,但系数的不同也是对算法效率的重要改进。

    最后辨析两个概念:算法运行时间和算法时间复杂度。算法运行时间T(n)一般用基本操作的次数表示。给定某个输入规模,就可以用T(n)精确表示该算法基本操作的次数。而时间复杂度一般用T(n)的渐进表达式g(n)表示,可以理解成, ∃ n 0 , c > 0 \exists n_0, c>0 n0,c>0,for ∀ n > n 0 \forall n>n_0 n>n0 T ( n ) T(n) T(n)增长和 c g ( n ) cg(n) cg(n)的增长存在一个稳定的关系。这种表示实际上是对运行时间增长速度的刻画,也可以看成是运行时间的一种近似,在算法效率的比较中往往更有价值。常用的渐进关系有:渐进上界 O ( n ) O(n) O(n)、渐进确界 Θ ( n ) \Theta(n) Θ(n)、渐进下界 Ω ( n ) \Omega(n) Ω(n)

    展开全文
  • 感知机算法中的优化方法的几何解释 针对非线性可分数据问题的解决 Pocket Algorithm算法

    感知机算法中的优化方法的几何解释

    本部分参考台湾大学林轩田教授机器学习基石课程—PLA部分

    PLA算法只有在出现错误分类的时候,才去调整w和b的值,使得错误分类减少。假设我们遇到的数据点(xn,yn)是我们第t次分类错误,那么就有因为是二分类问题,所以只会出现以下两种错误分类的情况:

    • 第一种:当yn=+1 时,则我们的错误结果为wTxn=wt∗xn=||w||∗||xn||∗cosΘ<0,即cosΘ<0 则Θ太大,为了能过纠正错误,决定减小Θ,就让w(t+1)=wt+x,紫色为改正之后的w(t+1)
    • 同理,对于第二种情况,当yn=-1的时候,则我们的错误结果为wTxn=wt∗xn=||w||∗||xn||∗cosΘ>0,即cosΘ>0 则Θ太小,为了能过纠正错误,决定增大Θ,就让w(t+1)=wt-x,紫色为改正之后的w(t+1)。

    综上所述,当分割线遇到点(xn,yn)时,如果分割正确,那么wt就不变,如果分割错误,那么就令
    注意w是分割线wTx=0的法线,也就是说分割线的方向是与w的方向垂直的。。。

    思考

    PLA 的优点是算法思路比较简单,易于实现。然而这个算法最大的缺点是假设了数据是线性可分的,然而事先并无法知道数据是否线性可分的。假如将PLA 用在线性不可分的数据中时,会导致PLA永远都无法对样本进行完全正确分开从而陷入到死循环中。
    如下图所示,当实例点并不是线性可分的时候,根本找不到一条直线或者一个超平面来完全划分开两类数据,只能利用曲线或者超曲面来划分。

    为了避免上面线性不可分的情况,将PLA的条件放宽一点,不再要求所有的样本都能正确的分开,而是要求犯错误的样本尽可能的少,即将问题变为了:

    也是就是说去寻找一条犯错误最少的线或者超平面。

    其实,从实际意义上,是不能的。这是一个著名的NP hard 问题!!!因为线有无穷多个啊!!!无法求得其最优解,因此只能求尽可能接近其最优解的近似解。林教授的课程讲义中提出的一种求解其近似解的算法 Pocket Algorithm(口袋算法,一种贪心算法)。

    Pocket Algorithm(口袋算法)

    口袋算法基于贪心的思想,他总是让遇到的最好的线(或者超平面)拿在自己手里。简单介绍一下:首先,我们有一条分割线wt,将数据实例不断带入,发现数据点(xn,yn)再上面出现错误分类,那么我们就纠正分割线得到w(t+1),然后我们让wt和w(t+1)遍历所有的数据,看一下哪条线犯的错误少,那么就让w(t+1)代替wt,否则wt不变。

    那么如何让算法停下来呢?

    由于口袋算法得到的线越来越好(PLA就不一定了,PLA是最终结果最好,其他情况就不一定是什么样子,不一定是越来越好),所以我们就自己规定迭代的次数。

    思考?

    答案是:PLA更好。先不说PLA可以找到最好的那条线。单从效率上来说,PLA也更好些。最主要的原因是,pocket algorithm 每次比较的时候,都要遍历所有的数据点,且两个算法都要遍历一遍,才会决定那个算法好,而这还是比较一次,如果我们让他迭代500次的,那就麻烦了!!!但是,所有前提是,数据是线性可分的。如果线性不可分,只能用pocket algorithm,因为PLA根本不会停下来(而且PLA的wt也不是每更改一次效果就会比之前的好)!!
    

    与PLA的比较:

    1、Pocket Algorithm事先设定迭代次数,而不是等着算法自己收敛到最优。
    2、随机遍历数据集,而不是循环遍历。
    3、遇到错误点校正时,只有当新得到的w对于所有的数据优于旧w的时候(也就是整体错误更少的时候)才更新,而PLA算法中,只要出现错误分类就更新。由此也可知,pocket Algorithm算法是保证每次得到的线或这面是越来越好的,而PLA算法不一定。而且,由于Pocket要比较错误率,需要计算所有的数据点,因此效率要地域PLA。所以在线性可分的数据集上,使用PLA算法,而不选择使用Pocket算法。但是,只要迭代次数足够多,Pocket和PLA的效果是一样的,都能够把数据完全正确分开,只是速度慢。
    

    代码实现

    下面,我们用Python来实现pocket Algorithm算法。

    # -*- encoding:utf-8 -*-
    '''
    @author=Ada
    Python实现的pocket algoritm
    '''
    
    from numpy import vectorize
    import numpy as np
    import matplotlib.pyplot as plt
    
    class Pocket:
    
        def __init__(self,random_state=None):
            self.numberOfIter=7000#最大迭代次数
            self.minWeights=None
            self.intercept=None#bias 截距
            self.errorCountArr=np.zeros(7000)#统计每次迭代的出错数
            self.errorCount=[]#统计每次优化或者每个更新权值时候的出错次数
            self.minErrors=7000#出错数量的初始值,一开始一般设置一个比较大的值
            self.random_state=random_state
    
        def predict(self,z):
            if z<0:
                return -1
            else:
                return 1
    
        def checkPredictedValue(self,z,actualZ):
            if(z==actualZ):
                return True
            else:
                return False
    
        def fit(self,X,Y):
            row,col=X.shape
            weights=np.array([1.0,1.0,1.0,1.0])
            vpredict = vectorize(self.predict)
            vcheckPredictedValue=vectorize(self.checkPredictedValue)
            learning_rate=1.0
            bias_val=np.ones((row,1))
            data=np.concatenate((bias_val,X),axis=1)
            np.random.seed(self.random_state)
            count=0
            iter=0
            while self.numberOfIter>0:
                weightedSum=np.dot(data,weights)
                predictedValues=vpredict(weightedSum)
                predictions=vcheckPredictedValue(predictedValues,Y)
                misclassifiedPoints=np.where(predictions==False)#分类错误的数据
                misclassifiedPoints=misclassifiedPoints[0]
                numOfErrors=len(misclassifiedPoints)#分类错误的数据量
                self.errorCountArr[iter]=numOfErrors
                if numOfErrors<self.minErrors:
                    self.minErrors=numOfErrors
                    self.errorCount.append(self.minErrors)
                    count+=1
                iter+=1
                misclassifiedIndex=np.random.choice(misclassifiedPoints)#这一步与PLA不同,
                                                                        # 在此是随机从错误数据点里面选择一个点,进行更新权值
                weights+=(Y[misclassifiedIndex]*learning_rate*data[misclassifiedIndex])
                self.numberOfIter-=1
            self.weights=weights[1:]
            self.intercept=weights[0]
    
    def main():
        data=np.loadtxt('classification.txt',dtype='float',delimiter=',',usecols=(0,1,2,4))
        X=data[:,0:3]
        Y=data[:,3]
        p=Pocket(random_state=2308863)
        p.fit(X,Y)
        print "Weights:"
        print p.weights
        print "Intercept Value:"
        print p.intercept
        print "Minimum Number Of Errors:"
        print p.minErrors
        ax1=plt.subplot(121)
        ax1.plot(np.arange(0,7000),p.errorCountArr)
        ax2=plt.subplot(122)
        ax2.plot(np.arange(0,len(p.errorCount)),p.errorCount)
        plt.show()
    
    if __name__ == "__main__":
        main()

    实验结果:Weights:[-0.43701921 -0.10683611 0.34784736]
    Intercept Value: -1.0
    Minimum Number Of Errors:935

    这里写图片描述

    上图的第一幅表示的是每次迭代时的出错数,第二幅图表示的每次更新权重时的出错数。通过上图可以观察到,在7000次迭代过程中,每次迭代出错数是不固定的,而每次更新时出错数是递减的。而且,7000词迭代过程中只有十次左右的更新操作。

    参考资料:

    1、机器学习基石—PLA
    2、台湾大学林轩田教授机器学习基石课程理解及python实现—-PLA
    3、分类系列之感知器学习算法PLA 和 口袋算法Pocket Algorithm
    4、听课笔记(第二讲): Perceptron-感知机 (台湾国立大学机器学习基石)

    《完》

    人生如棋,落子无悔!
                           ------- By Ada
    
    展开全文
  • 文章目录1、前言2、题目汇总3、二模板4、二流程5、二高频题详解5.1、LeetCode 33. 搜索旋转排序数组5.2、LeetCode ... 在排序数组中查找元素的第一个和最后一个位置 1、前言 二查找也称折半查找(Binary Search
  • 如何评价一个算法的好坏

    万次阅读 2019-04-27 21:38:39
    首先,这个算法必须是正确的 其次,好的算法应该是友好的,便于人们理解和交流,并且是机器...定义:在计算机科学中,算法的时间复杂度是一个函数,他定量描述了该算法的运行时间.一个算法执行所耗费的时间,从理论上...
  • 2、代收集算法,是基于这样一个事实:不同的对象的生命周期是不一样的。因此,不同生命周期的对象可以采取不同的收集方式,以便提高回收效率。一般是把Java堆分为新生代和老年代,这样就可以根据各个年代的特点...
  • 算法效率衡量标准(时间复杂度)

    千次阅读 2019-08-14 11:20:27
    如果对于解决一个问题有2种算法算法1的执行时间小于算法2,这并不能代表算法1优于算法2。假设执行算法1的计算机性能和环境都低于执行算法2的计算机的性能和环境,那么算法1可能执行的时间会更长。所以可以看出仅仅...
  • 主流链片技术和共识算法

    万次阅读 2021-12-31 15:47:45
    Harmony 是一个基于状态片和 PoS 的高性能公链项目,它的片架构由一条信标链和多条片链组成,信标链提供包括去中心化的随机数,片链 Header 的验证,接受验证节点的权益抵押等服务。 Harmony 怎么保证片...
  • 从今天开始,我将正式开启一个新的打卡专题——【数据结构·水滴计划】,没错!这是今年上半年的一整个系列计划!本专题目的是通过百天刷题计划,通过题目和知识点串联的方式,刷够1000道题!完成对数据结构相关知识...
  • 大部分的排序算法都有两个基本的操作:(1)比较两个关键字的大小.(2)将记录从一个位置移动到另一个位置。 排序算法分类  根据完成整个排序过程是否需要访问外存分为内部排序、外部排序。一般进行的是内部...
  • 算法交易分类大全

    千次阅读 2019-07-02 10:50:12
    算法交易又被称为自动交易、黑盒交易或者机器交易,它指的是通过使用计算机程序来发出交易指令的方法。在交易中,程序可以决定的范围包括交易时间的选择、交易的价格、甚至可以包括最后需要成交的证券数量。 算法...
  • 查找算法及其变种详解

    千次阅读 多人点赞 2019-02-15 21:11:47
    背景: 春节已过,开工大吉!...二查找针对的是一个有序的数据集合,查找思想有点类似分治思想。每次都通过跟区间的中间元素对比,将待查找的区间缩小之前的一半,直到找到要查找的元素,或者区间被...
  • 在前文了解到如何判断Java对象已经死亡,下面来了解Java虚拟机垃圾回收的几种常见算法:标记-清除算法、复制算法、标记-整理算法代收集算法、火车算法,介绍它们的算法思路,有什么优点和缺点,以及主要应用场景...
  • 数据挖掘算法——常用分类算法总结

    万次阅读 多人点赞 2019-06-17 10:55:22
    常用分类算法总结分类算法总结NBC算法LR算法SVM算法ID3算法C4.5 算法C5.0算法KNN 算法ANN 算法 分类算法总结 分类是在一群已经知道类别标号的样本中,训练种分类器,让其能够对某种未知的样本进行分类。分类算法...
  • 不知道大家有没有经常遇到这样的一个困扰,为什么同样的算法,你的程序却一直超时?大家用的都是暴力大法,为什么别人的能过所有数据,而你的却只能过前几个样例;同样都是使用dp,为什么你的比别人的慢了那么多,有...
  • GC垃圾代回收机制及算法

    千次阅读 2019-03-10 10:44:08
    java堆和方法区则不同,一个接口中多个实现类需要的内存不同,一个方法区需要的内存也可能不同,线程只有在运行时才知道创建了那些对象,这部分内存回收创建都是动态的。 判断哪些内存需要回收 方法: 1、引用计数...
  • 目录:算法分析与设计实验报告——二搜索算法的实现、 实验目的二、实验要求三、 实验原理四、 实验过程(步骤)五、 运行结果六、实验分析与讨论七、实验特色与心得附件 实验过程(步骤)附件二 运行结果 、 ...
  • 数据结构与算法必知基础知识

    千次阅读 多人点赞 2021-01-06 22:58:12
    原创公众号:bigsai 文章已收录在 全网都在关注的数据结构与算法学习仓库 欢迎star 前言 数据结构与算法是程序员内功体现的重要标准...为什么学习数据结构与算法?如果你还是学生,那么这门课程是必修的,考研基本也.
  • 摘自:腾讯游戏开发精粹(摘录次加深记忆方便查找,如有侵权 联系作者删除 谢谢) 如感兴趣,请购买原书支持
  • 测试使用K-最近邻(kNN)算法的30问题

    千次阅读 多人点赞 2020-09-25 22:57:20
    有趣的是,上月我们对这两种算法进行了技能测试。 如果你不熟悉机器学习,请确保在了解这两种算法的基础上进行测试。它们虽然简单,但是功能强大,并且在工业中得到广泛使用。此技能测试将帮助你在k最近邻算法上...
  • KNN算法理解

    千次阅读 2018-08-17 13:18:46
    算法概述 1、kNN算法又称为k近邻分类(k-nearest neighbor classification)算法。 最简单平凡的分类器也许是那种死记硬背式的分类器,记住所有的训练数据,对于新的数据则直接和训练数据匹配,如果存在相同属性...
  • 由于文章有点多,并且发的文章也不是一个系列一个系列发的,不过我的文章大部分都是围绕着 数据结构 + 算法 + 计算机网络 + 操作系统 + Linux + 数据库 这几个方面发的,为了方便大家阅读,我整理了一波。...
  • 尤其是在就业一年比一年难的情况下,经历过好多次心态崩裂,也问过很多人,来总结一下如果想成为一个【深度学习 CV 算法工程师】需要什么学习能力和知识储备。 这个文章应该会是一个【记录】的文章,看看自己这一路...
  • Leetcode算法题分类解析:()总览

    万次阅读 2016-06-17 23:01:03
    Leetcode算法题分类解析:()总览1.为何/如何刷题1.1 必要性刷题刷题,从“刷”字就能看出其中的机械性和...1.2 分类攻破为什么要这么麻烦地分类呢?照着Leetcode的题目顺序做不就好了?个人觉得分类有几动机:
  • 实验背景 为了降低难度,我们以读取纯文本文件例,把内容分行加密后再写到另一个文件中,最后计算时长(解密相反); 测试项目在我本地,在Junit测试单元上设置JVM内存配置(-Xmx1024M -Xms1024M); 由于知道 ...
  • 它是一个衡量算法优劣的重要指标,按照所需资源的又细分时间复杂度和空间复杂度。 时间复杂度:运行算法所需的时间随着数据量变化关系,记做T(n),n为算法的规模。 空间复杂度:一个算...
  • 路径规划算法

    万次阅读 多人点赞 2021-11-14 10:20:44
    文章目录前言、传统路径规划算法1.Dijkstra算法2.A*算法3.D*算法4.人工势场法二、基于采样路径规划算法1.PRM算法2.RRT算法三、智能仿生算法1.神经网络算法2.蚁群算法3.遗传算法 前言 随着机器人技术、智能控制...
  • 算法复杂度分为时间复杂度和空间复杂度。 时间复杂度用于度量算法执行的时间长短;而空间复杂度则是用于度量算法所需存储空间的大小。 目录 时间复杂度 ...算法的时间复杂度(计算实例) ... 大O记号 二 Ω记号...
  • 主宰操作系统的经典算法

    万次阅读 多人点赞 2020-07-24 15:22:50
    进程和线程在调度时候出现过很多算法,这些算法的设计背景是当一个计算机是多道程序设计系统时,会频繁的有很多进程或者线程来同时竞争 CPU 时间片。 那么如何选择合适的进程/线程运行是一项艺术。当两个或两个以上...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 332,746
精华内容 133,098
关键字:

一个算法的效率可分为什么