精华内容
下载资源
问答
  • 算法效率与复杂度

    千次阅读 2018-05-29 20:57:13
    有穷性: 算法在有限的步骤之后会自动结束而不会无限循环,并且每一个步骤可以在接受的时间内完成 确定性:算法中的每一步都有确定的含义,不会出现二义性 可行性:算法的每一步都是可行的,也就是说每一步都能够...

    1,what is 算法

    算法的五大特性

    1. 输入: 算法具有0个或多个输入
    2. 输出: 算法至少有1个或多个输出
    3. 有穷性: 算法在有限的步骤之后会自动结束而不会无限循环,并且每一个步骤可以在可接受的时间内完成
    4. 确定性:算法中的每一步都有确定的含义,不会出现二义性
    5. 可行性:算法的每一步都是可行的,也就是说每一步都能够执行有限的次数完成

    我举个栗子:如果 a+b+c=100,且 a^2+b^2=c^2(a,b,c 为自然数),如何求出所有a、b、c可能的组合?

    In [3]: import time
       ...:
       ...: start_time = time.time()
       ...:
       ...: # 注意是三重循环
       ...: for a in range(0, 101):
       ...:     for b in range(0, 101):
       ...:         for c in range(0, 101):
       ...:             if a**2 + b**2 == c**2 and a+b+c == 100:
       ...:                 print("a, b, c: %d, %d, %d" % (a, b, c))
       ...:
       ...: end_time = time.time()
       ...: print("elapsed: %f" % (end_time - start_time))
       ...: print("complete!")
       ...:
    

    运行结果:

    a, b, c: 0, 50, 50
    a, b, c: 50, 0, 50
    elapsed: 1.564089
    complete!
    
    In [4]:

    我本来还想求 a+b+c=1000 的,可以我电脑死机了。没办法,电脑CPU太差了,运行不了。所以就选了100.(偷偷告诉你,500我电脑都不行)。
    注意运行时间哈
    现在换个算法:

    
    In [4]: import time
       ...:
       ...: start_time = time.time()
       ...:
       ...: # 注意是两重循环
       ...: for a in range(0, 101):
       ...:     for b in range(0, 101-a):
       ...:         c = 100 - a - b
       ...:         if a**2 + b**2 == c**2:
       ...:             print("a, b, c: %d, %d, %d" % (a, b, c))
       ...:
       ...: end_time = time.time()
       ...: print("elapsed: %f" % (end_time - start_time))
       ...: print("complete!")
       ...:

    运行结果:

    a, b, c: 0, 50, 50
    a, b, c: 50, 0, 50
    elapsed: 0.009000
    complete!
    
    In [5]:

    看到时间差了吧。这就是算法对程序运行效率的影响。一般来说,执行时间能够在一定程度上反应算法的效率,所以称之为时间复杂度

    2,时间复杂度与“大O记法”

    我们假定计算机执行算法每一个基本操作的时间是固定的一个时间单位,那么有多少个基本操作就代表会花费多少时间单位。算然对于不同的机器环境而言,确切的单位时间是不同的,但是对于算法进行多少个基本操作(即花费多少时间单位)在规模数量级上却是相同的,由此可以忽略机器环境的影响而客观的反应算法的时间效率。

    对于算法的时间效率,我们可以用“大O记法”来表示。
    “大O记法”:对于单调的整数函数f,如果存在一个整数函数g和实常数c>0,使得对于充分大的n总有f(n)<=c*g(n),就说函数g是f的一个渐近函数(忽略常数),记为f(n)=O(g(n))。也就是说,在趋向无穷的极限意义下,函数f的增长速度受到函数g的约束,亦即函数f与函数g的特征相似。
    时间复杂度:假设存在函数g,使得算法A处理规模为n的问题示例所用时间为T(n)=O(g(n)),则称O(g(n))为算法A的渐近时间复杂度,简称时间复杂度,记为T(n)

    时间复杂度有几种分类:

    • 算法完成工作最少需要多少基本操作,即最优时间复杂度
    • 算法完成工作最多需要多少基本操作,即最坏时间复杂度
    • 算法完成工作平均需要多少基本操作,即平均时间复杂度

    而我们平时所说的时间复杂度,一般都是指最坏时间复杂度

    时间复杂度的几条基本计算规则:

    • 基本操作,即只有常数项,认为其时间复杂度为O(1)
    • 顺序结构,时间复杂度按加法进行计算
    • 循环结构,时间复杂度按乘法进行计算
    • 分支结构,时间复杂度取最大值
    • 判断一个算法的效率时,往往只需要关注操作数量的最高次项,其它次要项和常数项可以忽略
    • 在没有特殊说明时,我们所分析的算法的时间复杂度都是指最坏时间复杂度

    2,常见的时间复杂度

    执行次数函数举例 非正式术语
    12 O(1) 常数阶
    2n+3 O(n) 线性阶
    3n2+2n+1 O(n^2) 平方阶
    5log2n+20 O(logn) 对数阶
    2n+3nlog2n+19 O(nlogn) nlogn阶
    6n3+2n2+3n+4 O(n^3) 立方阶
    2n O(2n) 指数阶

    注意,经常将log2n(以2为底的对数)简写成logn

    常见时间复杂度之间的关系:
    这里写图片描述
    所消耗的时间从小到大

    O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

    3,数据结构

    定义:数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下,精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。
    数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成。记为:
    Data_Structure=(D,R)
    其中D是数据元素的集合,R是该集合中所有元素之间的关系的有限集合。—-来自百科

    看不懂是吧,我也是。我觉得所谓的数据结构大抵就是数据的类型以及数据储存方式的一个集合。

    算法与数据结构的区别:
    数据结构只是静态的描述了数据元素之间的关系。

    高效的程序需要在数据结构的基础上设计和选择算法。

    程序 = 数据结构 + 算法

    In a word:算法是为了解决实际问题而设计的,数据结构是算法需要处理的问题载体

    Conclusion:

    不会算法的程序猿不是好程序猿。

    展开全文
  • Java 二查找算法效率比较

    千次阅读 2014-08-10 17:30:56
    1.前提:二查找的前提是需要查找的数组必须是已排序的,我们这里的实现默认升序 ...然后依次是一个递归过程,将前半部分或者后半部分继续分解三部分。 能描述得不是很清楚,若是不理解可以去网

    1.前提:二分查找的前提是需要查找的数组必须是已排序的,我们这里的实现默认为升序

    2、原理:将数组分为三部分,依次是中值(所谓的中值就是数组中间位置的那个值)前,中值,中值后;将要查找的值和数组的中值进行比较,若小于中值则在中值前面找,若大于中值则在中值后面找,等于中值时直接返回。然后依次是一个递归过程,将前半部分或者后半部分继续分解为三部分。可能描述得不是很清楚,若是不理解可以去网上找。从描述上就可以看出这个算法适合用递归来实现,可以用递归的都可以用循环来实现。所以我们的实现分为递归和循环两种,可以根据代码来理解算法

     

    package com.cn;
    //二分查找法
    public class BinarySearch {
    	public static void main(String[] args){
    		int searchArr[] = new int[1000000];
    		for(int i=0;i<1000000;i++){
    			searchArr[i]=i;
    		}
    		System.out.println(binSearch(searchArr,0,searchArr.length-1,99));
    		System.out.println(binSearch(searchArr,99));
    	}
    	public static int binSearch(int arr[], int start,int end,int sear){
    		int mid = (end-start)/2 + start;
    		if(sear==arr[mid]){
    			return mid;
    		}
    		
    		if(start>=end){
    			return -1;
    		}else if(sear < arr[mid]){
    			return binSearch(arr,0,mid-1,sear);
    		}else if(sear >arr[mid]){
    			return binSearch(arr,mid+1,end,sear);
    		}
    		return -1;
    	}
    	public static int binSearch(int arr[],int key){
    		int mid = arr.length/2;
    		
    		int start = 0;
    		int end = arr.length-1;
    		while(start<=end){
    			mid = (end-start)/2+start;
    			if(key ==arr[mid]){
    				return mid;
    			}else if(key <= arr[mid]){
    				end = mid-1;
    			}else if(key >=arr[mid]){
    				start = mid+1;
    			}
    		}
    		return -1;
    	}
    	
    }
    


    效率比较:

    循环二分查找算法的效率高于递归二分查找算法

     

    展开全文
  • 算法

    万次阅读 2018-02-08 00:13:09
    1.算法定义 ...如果一个算法有缺陷,或不适合于某个问题,执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

    1.算法定义

    算法(Algorithm)是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制。也就是说,能够对一定规范的输入,在有限时间内获得所要求的输出。如果一个算法有缺陷,或不适合于某个问题,执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

    一个算法应该具有以下七个重要的特征:
    ①有穷性(Finiteness):算法的有穷性是指算法必须能在执行有限个步骤之后终止;
    ②确切性(Definiteness):算法的每一步骤必须有确切的定义;
    ③输入项(Input):一个算法有0个或多个输入,以刻画运算对象的初始情况,所谓0个输 入是指算法本身定出了初始条件;
    ④输出项(Output):一个算法有一个或多个输出,以反映对输入数据加工后的结果。没 有输出的算法是毫无意义的;
    ⑤可行性(Effectiveness):算法中执行的任何计算步骤都是可以被分解为基本的可执行 的操作步,即每个计算步都可以在有限时间内完成(也称之为有效性);
    ⑥高效性(High efficiency):执行速度快,占用资源少;
    ⑦健壮性(Robustness):对数据响应正确。

    2. 时间复杂度

    计算机科学中,算法的时间复杂度是一个函数,它定量描述了该算法的运行时间,时间复杂度常用大O符号(大O符号(Big O notation)是用于描述函数渐进行为的数学符号。更确切地说,它是用另一个(通常更简单的)函数来描述一个函数数量级的渐近上界。在数学中,它一般用来刻画被截断的无穷级数尤其是渐近级数的剩余项;在计算机科学中,它在分析算法复杂性的方面非常有用。)表述,使用这种方式时,时间复杂度可被称为是渐近的,它考察当输入值大小趋近无穷时的情况。

    大O,简而言之可以认为它的含义是“order of”(大约是)。

    无穷大渐近

    大O符号在分析算法效率的时候非常有用。举个例子,解决一个规模为 n 的问题所花费的时间(或者所需步骤的数目)可以被求得:T(n) = 4n^2 - 2n + 2。 当 n 增大时,n^2; 项将开始占主导地位,而其他各项可以被忽略——举例说明:当 n = 500,4n^2; 项是 2n 项的1000倍大,因此在大多数场合下,省略后者对表达式的值的影响将是可以忽略不计的。

    3.时间复杂度计算方法

    1.一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试,只需知道哪个算法花费的时间多,哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多。
    一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。

    2.一般情况下,算法的基本操作重复执行的次数是模块n的某一个函数f(n),因此,算法的时间复杂度记做:T(n)=O(f(n))。随着模块n的增大,算法执行的时间的增长率和f(n)的增长率成正比,所以f(n)越小,算法的时间复杂度越低,算法的效率越高。
    在计算时间复杂度的时候,先找出算法的基本操作,然后根据相应的各语句确定它的执行次数,再找出T(n)的同数量级(它的同数量级有以下:1,Log2n ,n ,nLog2n ,n的平方,n的三次方,2的n次方,n!),找出后,f(n)=该数量级,若T(n)/f(n)求极限可得到一常数c,则时间复杂度T(n)=O(f(n))。

    3.常见的时间复杂度
    按数量级递增排列,常见的时间复杂度有:
    常数阶O(1), 对数阶O(log2n), 线性阶O(n), 线性对数阶O(nlog2n), 平方阶O(n^2), 立方阶O(n^3),…, k次方阶O(n^k), 指数阶O(2^n) 。

    其中,
    1.O(n),O(n^2), 立方阶O(n^3),…, k次方阶O(n^k) 为多项式阶时间复杂度,分别称为一阶时间复杂度,二阶时间复杂度。。。。
    2.O(2^n),指数阶时间复杂度,该种不实用
    3.对数阶O(log2n), 线性对数阶O(nlog2n),除了常数阶以外,该种效率最高
    例:算法:
      for(i=1;i<=n;++i)
      {
         for(j=1;j<=n;++j)
         {
             c[ i ][ j ]=0; //该步骤属于基本操作 执行次数:n^2
              for(k=1;k<=n;++k)
                   c[ i ][ j ]+=a[ i ][ k ]*b[ k ][ j ]; //该步骤属于基本操作 执行次数:n^3
         }
      }
      则有 T(n)= n^2+n^3,根据上面括号里的同数量级,我们可以确定 n^3为T(n)的同数量级
      则有f(n)= n^3,然后根据T(n)/f(n)求极限可得到常数c
      则该算法的 时间复杂度:T(n)=O(n^3)
    

    4.讨论

    定义:如果一个问题的规模是n,解这一问题的某一算法所需要的时间为T(n),它是n的某一函数 T(n)称为这一算法的“时间复杂性”。

    当输入量n逐渐加大时,时间复杂性的极限情形称为算法的“渐近时间复杂性”。

    我们常用大O表示法表示时间复杂性,注意它是某一个算法的时间复杂性。大O表示只是说有上界,由定义如果f(n)=O(n),那显然成立f(n)=O(n^2),它给你一个上界,但并不是上确界,但人们在表示的时候一般都习惯表示前者。

    此外,一个问题本身也有它的复杂性,如果某个算法的复杂性到达了这个问题复杂性的下界,那就称这样的算法是最佳算法。

    “大O记法”:在这种描述中使用的基本参数是 n,即问题实例的规模,把复杂性或运行时间表达为n的函数。这里的“O”表示量级 (order),比如说“二分检索是 O(logn)的”,也就是说它需要“通过logn量级的步骤去检索一个规模为n的数组”记法 O ( f(n) )表示当 n增大时,运行时间至多将以正比于 f(n)的速度增长。

    这种渐进估计对算法的理论分析和大致比较是非常有价值的,但在实践中细节也可能造成差异。例如,一个低附加代价的O(n2)算法在n较小的情况下可能比一个高附加代价的 O(nlogn)算法运行得更快。当然,随着n足够大以后,具有较慢上升函数的算法必然工作得更快。

    O(1)
    
    Temp=i;i=j;j=temp;                    
    
    以上三条单个语句的频度均为1,该程序段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶,记作T(n)=O(1)。如果算法的执行时间不随着问题规模n的增加而增长,即使算法中有上千条语句,其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。
    
    O(n^2)
    
    2.1. 交换i和j的内容
         sum=0;                 (一次)
         for(i=1;i<=n;i++)       (n次 )
            for(j=1;j<=n;j++) (n^2次 )
             sum++;       (n^2次 )
    解:T(n)=2n^2+n+1 =O(n^2)
    
    2.2.   
        for (i=1;i<n;i++)
        {
            y=y+1;         ①   
            for (j=0;j<=(2*n);j++)    
               x++;        ②      
        }         
    解: 语句1的频度是n-1
              语句2的频度是(n-1)*(2n+1)=2n^2-n-1
              f(n)=2n^2-n-1+(n-1)=2n^2-2
              该程序的时间复杂度T(n)=O(n^2).         
    
    O(n)      
                                                          
    2.3.
        a=0;
        b=1;                      ①
        for (i=1;i<=n;i++) ②
        {  
           s=a+b;    ③
           b=a;     ④  
           a=s;     ⑤
        }
    解:语句1的频度:2,        
               语句2的频度: n,        
              语句3的频度: n-1,        
              语句4的频度:n-1,    
              语句5的频度:n-1,                                  
              T(n)=2+n+3(n-1)=4n-1=O(n).
                                                                                                     
    O(log2n )
    
    2.4.
         i=1;       ①
        while (i<=n)
           i=i*2; ②
    解: 语句1的频度是1,  
              设语句2的频度是f(n),   则:2^f(n)<=n;f(n)<=log2n    
              取最大值f(n)= log2n,
              T(n)=O(log2n )
    
    O(n^3)
    
    2.5.
        for(i=0;i<n;i++)
        {  
           for(j=0;j<i;j++)  
           {
              for(k=0;k<j;k++)
                 x=x+2;  
           }
        }
    解:当i=m, j=k的时候,内层循环的次数为k当i=m时, j 可以取 0,1,...,m-1 , 所以这里最内循环共进行了0+1+...+m-1=(m-1)m/2次所以,i从0取到n, 则循环共进行了: 0+(1-1)*1/2+...+(n-1)n/2=n(n+1)(n-1)/6所以时间复杂度为O(n^3).
    

    我们还应该区分算法的最坏情况的行为和期望行为。如快速排序的最 坏情况运行时间是 O(n^2),但期望时间是 O(nlogn)。通过每次都仔细地选择基准值,我们有可能把平方情况 (即O(n^2)情况)的概率减小到几乎等于 0。在实际中,精心实现的快速排序一般都能以 (O(nlogn)时间运行。

    下面是一些常用的记法:
    访问数组中的元素是常数时间操作,或说O(1)操作。一个算法如 果能在每个步骤去掉一半数据元素,如二分检索,通常它就取 O(logn)时间。用strcmp比较两个具有n个字符的串需要O(n)时间。常规的矩阵乘算法是O(n^3),因为算出每个元素都需要将n对 元素相乘并加到一起,所有元素的个数是n^2。
    指数时间算法通常来源于需要求出所有可能结果。例如,n个元 素的集合共有2n个子集,所以要求出所有子集的算法将是O(2n)的。指数算法一般说来是太复杂了,除非n的值非常小,因为,在 这个问题中增加一个元素就导致运行时间加倍。不幸的是,确实有许多问题 (如著名的“巡回售货员问题” ),到目前为止找到的算法都是指数的。如果我们真的遇到这种情况,通常应该用寻找近似最佳结果的算法替代之。

    5.常用排序

    这里写图片描述

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

    算法设计策略

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

    蛮力法

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

    减治法

    减治法思想

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

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

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

    算法设计中的递推类型

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

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

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

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

    算法思想

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

    过程

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

    代码

    伪代码

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

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

    算法思想

    对象:拓扑结构

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

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

    BFS & DFS

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

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

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

    过程

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

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

    在广优搜索过程中,会形成一棵广度优先树,所谓广度优先树,就是一个描述节点被发现过程的树结构,其根节点即为搜索开始时的源节点s。广优树一个重要的性质就是可以确定最短路径。到达每个节点时经历的边数 dd 即为源节点到该节点的最短路径。这个结论是由严谨的证明推导出来的,但从直观上也比较容易理解,关键要抓住这个结论成立的前提条件:图中各边的权重都是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],每个点的邻接链表扫了一遍搜索即结束。加和,即需要执行vVAdj[v]\sum_{v\in V}Adj[v] 次。这个数字大小和数据存储格式有关。若以邻接链表的形式存储,上文中说到图G的邻接链表长度之和为O(E),则需执行O(E)次,故DFS过程总的复杂度为O(V+E)。对于邻接矩阵形式存储的数据,复杂度即为O(V2)O(V^2)
    从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(V2)O(V^2)

    附:算法效率度量详解

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

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

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

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

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

    展开全文
  • 大部分的排序算法都有两个基本的操作:(1)比较两个关键字的大小.(2)将记录从一个位置移动到另一个位置。 排序算法分类  根据完成整个排序过程是否需要访问外存分为内部排序、外部排序。一般进行的是内部...
  • 目标跟踪算法的分类(

    万次阅读 多人点赞 2015-09-14 11:41:37
    运动目标跟踪主流算法大致分类 主要基于两种思路: a)不依赖于先验知识,直接从图像序列中检测到运动目标,并进行目标识别,最终跟踪感兴趣的运动目标; b)依赖于目标的先验知识,首先运动目标建模,然后在图像...
  • 衡量算法效率最简单的一个办法就是把算法变成一个程序,然后再机器上执行,然后计时,这就是事后统计法。 这样显然有一些缺点: 1.必须到机器上去计算,而且这个计算不只是一次,我们要用多组数据对其进行重复的运算...
  • 如何评价一个算法的好坏

    千次阅读 2019-04-27 21:38:39
    首先,这个算法必须是正确的 其次,好的算法应该是友好的,便于人们理解和交流,并且是机器...定义:在计算机科学中,算法的时间复杂度是一个函数,他定量描述了该算法的运行时间.一个算法执行所耗费的时间,从理论上...
  • Leetcode算法题分类解析:()总览

    万次阅读 2016-06-17 23:01:03
    Leetcode算法题分类解析:()总览1.为何/如何刷题1.1 必要性刷题刷题,从“刷”字就能看出其中的机械性和...1.2 分类攻破为什么要这么麻烦地分类呢?照着Leetcode的题目顺序做不就好了?个人觉得分类有几动机:
  • 先来说一下为什么要看这本书,起因是最近刷LeetCode的时候,发现一个涉及到python数据结构的知识——链表,果然自己的python学习的还是有问题,所以趁此机会攻读一下算法和数据结构方面的书籍,继而有了这本书的读书...
  • Dijkstra 最短路径算法种高效率实现Dijkstra 最短路径算法种高效率实现Dijkstra 最短路径算法种高效率实现[日期:2005-2-7]武汉测绘科技大学学报 作者:乐阳 龚健雅摘 要 在已存在的一些最短路径算法...
  • 查找算法

    千次阅读 2016-10-01 11:30:32
    算法概述 当数据量很大时适宜采用二分法查找,其是效率较高的查找方法,但前提条件是要查找的集合必须是有序的,或是升序排列或是降序排列都可以。二分法又称折半查找,故名思意就是就是从中间开始比较查找,其...
  • 算法交易分类大全

    千次阅读 2019-07-02 10:50:12
    算法交易又被称为自动交易、黑盒交易或者机器交易,它指的是通过使用计算机程序来发出交易指令的方法。在交易中,程序可以决定的范围包括交易时间的选择、交易的价格、甚至可以包括最后需要成交的证券数量。 算法...
  • 算法的定义 ...如果一个算法有缺陷,或不适合于某个问题,执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。
  • 2、代收集算法,是基于这样一个事实:不同的对象的生命周期是不一样的。因此,不同生命周期的对象可以采取不同的收集方式,以便提高回收效率。一般是把Java堆分为新生代和老年代,这样就可以根据各个年代的特点...
  • 背景提取算法——帧间差法、背景差法、ViBe算法、ViBe+算法: 背景提取有很多算法。针对静止摄像机的帧间差法、高斯背景差法、ViBe背景提取算法以及它的改进算法ViBe+,还有针对运动摄像机的光流法等。 本文...
  • 八大排序算法

    万次阅读 多人点赞 2012-07-23 16:45:18
    排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,次不能容纳全部的排序记录,在排序过程中需要访问外存。 我们这里说说八大排序就是内部排序。 当n较大,则...
  • 在前文了解到如何判断Java对象已经死亡,下面来了解Java虚拟机垃圾回收的几种常见算法:标记-清除算法、复制算法、标记-整理算法代收集算法、火车算法,介绍它们的算法思路,有什么优点和缺点,以及主要应用场景...
  • 不知道大家有没有经常遇到这样的一个困扰,为什么同样的算法,你的程序却一直超时?大家用的都是暴力大法,为什么别人的能过所有数据,而你的却只能过前几个样例;同样都是使用dp,为什么你的比别人的慢了那么多,有...
  • JVM算法

    千次阅读 2018-08-07 15:08:01
    目前JVM虚拟机中基本都使用带收集算法,根据对象存活周期不同,分为三个年代:年青代、老年代、持久代。这是因为不同对象存活时间不一致,有些... 年青代包含一个eden区,两个survivor区,默认比例8:1:1。  ...
  • 五大常用算法:分治算法

    万次阅读 2018-03-14 12:49:45
    分治算法一、基本概念 在计算机科学中,分治法是一种很...这个技巧是很多高效算法的基础,如排序算法(快速排序,归并排序),傅立叶变换(快速傅立叶变换)…… 任何一个可以用计算机求解的问题所需的计算时间都与其...
  • 机器学习常见算法分类,算法优缺点汇总

    万次阅读 多人点赞 2017-04-14 12:08:13
    机器学习无疑是当前数据分析领域的一个热点内容。很多人在平时的工作中都或多或少会用到机器学习的算法。...这里,我们从两个方面来给大家介绍,第一个方面是学习的方式,第二个方面是算法的类似性。 学习方式 根
  • Java 代收集算法

    万次阅读 多人点赞 2016-07-31 15:02:39
    摘要当前商业虚拟机的垃圾收集都采用“代收集”(Generational Collection)算法,这种算法并没有什么新的思想,只是根据对象的存活周期的不同将内存划分几块。一般是把Java堆分为新生代和老年代,这样就可以...
  • 常用分类聚类算法

    千次阅读 2017-12-11 09:15:50
    什么是分类 分类任务就是明确对象属于哪个预定义的目标类。其中预定义的目标类是离散时分类,连续时回归。 有哪些分类方法 常用的分类算法有决策树,基于规则的分类算法,神经网络,支持向量机和朴素贝叶斯...
  • 文本分类常用算法比较

    万次阅读 2015-04-03 16:10:48
    本文对文本分类中的常用算法进行了小结,比较它们之间的优劣,为算法的选择提供依据。  、决策树(Decision Trees) 优点:  1、决策树易于理解和解释.人们在通过解释后都有能力去理解决策树所表达的意义。 ...
  • 数据挖掘算法——常用分类算法总结

    万次阅读 多人点赞 2019-06-17 10:55:22
    常用分类算法总结分类算法总结NBC算法LR算法SVM算法ID3算法C4.5 算法C5.0算法KNN 算法ANN 算法 分类算法总结 分类是在一群已经知道类别标号的样本中,训练种分类器,让其能够对某种未知的样本进行分类。分类算法...
  • 查找算法及其变种详解

    千次阅读 2019-02-15 21:11:47
    背景: 春节已过,开工大吉!...二查找针对的是一个有序的数据集合,查找思想有点类似分治思想。每次都通过跟区间的中间元素对比,将待查找的区间缩小之前的一半,直到找到要查找的元素,或者区间被...
  • 聚类分析是一种无监督机器学习(训练样本的标记信息是未知的)算法,它的目标是将相似的对象归到同一个簇中,将不相似的对象归到不同的簇中。如果要使用聚类分析算法对一堆文本分类,关键要解决这几个问题: 如何...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 288,563
精华内容 115,425
关键字:

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