精华内容
下载资源
问答
  • 算法——个人对算法的一些理解

    千次阅读 2018-02-05 14:08:49
    个人对算法的一些理解  在学校同学们之间,算法总是被放在一个非常高位置,有多高呢?嗯...就是非常非常高啦,高到有人只要能说出几个非常牛掰和算法有关名词,比如NP完全问题啦、模拟退火啦就觉得自己是...

                         个人对算法的一些理解

          在学校的同学们之间,算法总是被放在一个非常高的位置,有多高呢?嗯...就是非常非常高啦,高到有人只要能说出几个非常牛掰的和算法有关的名词,比如NP完全问题啦、模拟退火啦就觉得自己是大神了(其实有些人连快排都写不出来,或者写个快排还要先翻翻书)。其实我觉得算法跟数据结构、设计模式一样,都只是一种工具,用这样的工具能快速有效地解决一些实际问题,如果只知道算法,而不懂这些算法能够用于哪些场景,那么这些算法在这些人的大脑中是没有什么意义的。
         根据我的经验,算法对于大一的学生是“那个人算法很厉害,大神大神”,对于大二"你听说过模拟退火过没?你听说过遗传算法没?你听说过反馈神经网络没?现在的AI算法可以......",对于大三"嗯,算法很重要,以后工作有比没有好,工作中经常用到,平时有空闲的时间多研究研究,对未来的成长大大的有好处"。
          算法其实就是对一个问题或一类问题的解决过程的描述。比如说用加法求1加到100,那么就可以用
    count=0
    for i in 1...100
        count += i
    来描述。这个描述的过程就是不断的累加。算法非常关注于复杂度,也就是时间复杂度和空间复杂度。有些算法可以让时间用得尽量少,而有些算法为了节约空间,会用牺牲时间的方式来换取少用空间。不过,由于现在的物理储存设备的空间越来越大,空间暂时不是非常重要,除非在一些特殊的场景,比如说在大规模数据的情况下。当数据只有1M的时候,空间增加100倍没有什么很大的问题,但是如果数据有1T的话,再增加100倍后的数据量,是很难让人接受的。对于一个算法,我们经常需要在时间和空间之间进行取舍。
          算法跟程序不同,算法是对一个问题解决过程的描述,需要有0个或多个输入,至少1个输出,每个过程都是确定的,并且一定要有有限的时间内完成。但程序就不一定,有些程序可以一直运行下去,只有一直给机器供电,程序一直不出现致命错误。
          算法也可以一种模型,数据结构是对数据储存的模型,而算法是对问题解决过程的模型。数据结构是为了更方便的储存和访问数据,算法是为了更有效率地处理数据。所以算法和数据结构是不分家的,没有数据结构,算法根本没有数据可以操作,算法也无法进行,而没有算法,数据结构光储存有数据,这些数据不经处理,也大部分是无用的。
          经过无数计算机算法前辈的研究,已经有非常多现成的算法供我们学习和使用。算法并非是计算机专有的,或者说算法的思想来源于很多其他行业。比如说前面说到的模拟退火算法。算法还涉及到了很多微积分、线性代数、离散数学、概率论、博弈论、数论方面的知识。
          
    展开全文
  • 算法设计时,很重要一步需要确定其占用空间资源和时间资源,如果一个算法执行需要很长时间,那么它很难有什么用处。同样一个算法占用空间太大,很有可能目前大多数计算机都无法运行。这篇介绍是算法...

    “算法(algorithm)是为求解一个问题需要遵循的,被清楚地指定的简单指令集合。”

    算法设计时,很重要的一步需要确定其占用的空间资源和时间资源,如果一个算法执行需要很长的时间,那么它很难有什么用处。同样的一个算法占用的空间太大,很有可能目前大多数的计算机都无法运行。这篇介绍的是算法的时间复杂度。

    首先我们需要理解算法的时间复杂度是什么,其并不是一台计算机运行一个算法所花的时间。同样的一个算法在不同的计算机的运行时间是不同的,既与计算机的配置有关,也与计算机的使用时间有关,甚至于计算机所在的环境有关,所以算法执行的时间是难以确定的,也是没有太大意义的,因此需要找一个方式来作为专门比较算法的复杂度。使得在相同环境中算法的执行时间最低。

    为了解决这个问题引入一个时间复杂度的计算法则:大O记法。

    时间频度

    一个算法花费的时间与算法中语句执行的次数成正相关,算法中语句执行的次数称为时间频度或语句频度。记作T(n)。

    一般情况下,算法中语句的执行次数,是一个与那有关的函数,用T(n)来表示。若有一个辅助函数f(n),在当n趋近于无穷大时,T(n)/f(n)时的极限值趋近于一个不等于零常数值,则称f(n)为T(n)的同数量级函数。记作T(n)=O(f(n))。称O(f(n))为算法的时间复杂度。

    我们在这给出的是他们之间的相对级别,任意给定两个不同的函数,可能会存在某一个点使得f(n)>g(n),但就此我们说f(n)的算法复杂度高于g(n),这是这是没有意义的。于是我们比较的是其函数增长率。因此即使T(n)不同,但是其算法复杂度也可能相同。比如:T(n)=10n2+100n+100与T(n)=100n2+10n+200的时间复杂度是相同的都是O(n2)。

    常见的时间复杂度

    1. 常数阶:O(1)
    2. 对数阶:O(logn)
    3. 线性阶:O(n)
    4. 线性对数阶:O(nlogn)
    5. 次方阶:O(nk)
    6. 指数阶:O(2n)

    说明:

    其时间复杂度有小到大的排列关系为:O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(nk) < O(2n)

    举例

    • 对数阶 O(logn)
    for (int i = 1; i < n; i++)
    {
    	i = i * 2;
    }
    
    • 线性阶 O(n)
    int i = 1; 
    while (i < n)
    {
    	i++;
    }
    
    • 线性对数阶 O(nlogn)
    forint i = 1; i < n; i++)
    {
    	j = 1; 
    	while (j < n)
    	{
    		j = j * 2;
    	}
    }
    
    • 平方阶 O(n2)
    for (int i = 0; i < n; i++)
    {
    	for (int j = 0; j < n; j++)
    	{
    		int x = i; 
    		x++;
    	}
    }
    

    平均时间复杂度和最坏时间复杂度

    1. 平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下,该算法的运行时间
    2. 最坏情况下的时间复杂度称为最坏时间复杂度(大O记法)。一般讨论的时间复杂度均是最坏时间复杂度,因为最坏时间复杂度是算法在算法输入实例的上界,这样就保证了运行的时间不会比最坏情况更长。
    3. 平均时间复杂度和最坏时间复杂度是否一致,和算法有关。

    举例:(八个著名的排序算法^ _ ^)

    排序法 平均时间 最差时间 稳定性 额外空间 备注
    冒泡排序 O(n2) O(n2) 稳定 O(1) n较小时比较好
    简单选择排序 O(n2) O(n2) 不稳定 O(1) n较小时比较好
    直接插入排序 O(n2) O(n2) 稳定 O(1) 大部分已经排列好了的时候
    快速排序 O(nlogn) O(n2) 不稳定 O(nlogn) n较大时比较好
    归并排序 O(nlogn) O(nlogn) 稳定 O(1) n较大时比较好
    堆排序 O(nlogn) O(nlogn) 不稳定 O(1) n较大时比较好
    基数排序 O(logRB) O(logRB) 稳定 O(n) B是真数(0~9),R是基数(个十百)
    希尔(shell)排序 O(nlogn) O(ns) 1<s<2 不稳定 O(1) s是所选分组
    展开全文
  • 通过磁盘调度算法的设计,深入理解提高磁盘访问速度原理。 内容:实现最短寻道时间优先(SSTF)
  • 还记得自己在学校开设算法设计与分析》课程中所学知识,当时使用教科书好像是一位阿拉伯作者所著,书中代码均使用伪代码展示,当时觉得伪代码什么是不切实际,到现在才发现,如...

            算法很重要,不知道为什么到现在才发现算法的重要性,最近在学习一本很有趣味的书——《算法的乐趣》。为了防止在看完书后就把知识还回去现象的发生,决定在学习的过程中养成每天一篇算法文的习惯。

            还记得自己在学校开设的《算法设计与分析》课程中所学的知识,当时使用的教科书好像是一位阿拉伯作者所著,书中的代码均使用伪代码展示,当时觉得伪代码什么的真的是不切实际,到现在才发现,如果你不深入理解算法,那确实会产生一种伪代码不痛不痒的感觉,但是如果你把伪代码中的思路全部理解了之后然后去自己写出真正的代码后会发现伪代码是对代码精炼最好的东西。


          闲话不多说了,切入正题。

          首先,理清几个名词:匹配,最大匹配,完美匹配,稳定匹配:
          都以女孩子找男朋友为例子,阐述上述的几个概念。首先假设男生有一个集合,女生有一个集合,且他们两个集合的数量是相等的。

          ①匹配:一个女生找到一个男朋友就是一个匹配,这个匹配由一个女生和一个男生构成。

          ②最大匹配:每个男生和女生只在匹配中出现至多一次,将男生和女生按照某种方法匹配了之后剩下的没有匹配的男生或者女生的数量最少,就说完成了一次最大匹配。

          ③完美匹配 :  每个男生和女生只在匹配中出现至多一次,且男生和女生正好匹配完了,就说完成了一次完美匹配。

         ④ 稳定匹配:如果匹配是完美匹配而且匹配中不存在不稳定因素,则称匹配为稳定匹配。不稳定因素的定义如下:比如一组数量相等的男生和女生配对去舞会跳舞,每个男生均有一个自己的喜爱列表,在列表中,他越中意的女生越排在列表的前面,同样,每个女生也有一个自己的偏爱列表,男生在其中的排名越靠前,表明女生越中意这个男生,当完成一次完美匹配后检查匹配的结果,如果存在两对匹配:男生1,他匹配的女伴是11,男生2,他匹配的舞伴是22。但是男生1明明更喜欢女生22,女生22同时也更喜欢男生1。这样的匹配对就称为不稳定因素。只有同时满足是完美匹配而且不存在不稳定因素的匹配才称之为稳定匹配。


    匈牙利算法实施的对象是一个二分图,二分图的概念在算法课上也有所介绍,简而言之就是将图中的节点分为两个集合,图中的边的两个端点必须要在不同的集合中。

    匈牙利算法的思想用语言描述就是:

          假设二分图的节点分为平均分为两部分,分别存储在集合1和集合2中。对于集合1的节点1,先在第二部分找一个和他**有连线**的节点2,并**假设将该节点分配给节点1**,(即节点2被节点1占有了),进一步看节点2是否还是自由节点,当且仅当**结点2是自由节点**或**者虽然节点2不是自由节点,但是将当前匹配做稍许改动后可以将节点2变为自由节点时**,才将节点1与节点2相连。并将count做+1操作,表示完成了一对匹配。对集合1的所有节点进行这个操作,当最后的count值为集合1(或者集合2,因为两部分中节点个数相等)中节点的个数时,该匹配变成完美匹配,进而可以根据不确定因素的描述,对该完美匹配进行不确定因素的搜索,当不存在不确定因素时,此次匹配为稳定匹配。

    也可以用增广路径的相关知识来解释,增光路径的一个好的例子我就照搬了:

    https://www.cnblogs.com/logosG/p/logos.html

    原作者讲的很清楚明了哇,自己差距还很大!


    接下来上代码:

    #include<iostream>
    #include<string>
    #include<string.h>
    using namespace std;
    const int UNIT_COUNT = 5;  //二部图中X集合与Yj集合的节点个数
    
    //定义二部图中节点数据结构结构
    typedef struct tagPartner {
    	const char *name;
    	int current;                 //当前匹配的节点
    	int pCount;                 //与该节点相连的另一个二部图中节点集合中的节点的个数
    	int perfect[UNIT_COUNT];   //与之有连线的Y节点的编号
    }PARTNER;
    
    //定义表示二部图最大匹配的数据结构
    typedef struct tagMaxMatch {
    	int edge[UNIT_COUNT][UNIT_COUNT];
    	bool supposed_on_path[UNIT_COUNT];
    	int real_on_path[UNIT_COUNT];
    	int max_match;
    }MAX_MATCH;
    
    PARTNER X[] = {
    	 {"X1",-1, 1, {2}  },
    	 {"X2",-1, 2, {0,1}  },
    	 {"X3",-1, 3, {1,2,3}  },
    	 {"X4",-1, 2, {1,2}  },
    	 {"X5",-1, 3, {2,3,4}  },
    };
    PARTNER Y[] = {
    	{"Y1",-1, 1, {1}  },
    	{"Y2",-1, 3, {1,2,3}  },
    	{"Y3",-1, 4, {0,2,3,4}  },
    	{"Y4",-1, 2, {2,4}  },
    	{"Y5",-1, 1, {4}  },
    };
    bool FindAugmentPath(MAX_MATCH *match, int xi) {
    	for (int yj = 0; yj < UNIT_COUNT; yj++) {
    		if ((match->edge[xi][yj] == 1) && (!match->supposed_on_path[yj])) {
    			match->supposed_on_path[yj] = true;
    			if ((match->real_on_path[yj] == -1) || (FindAugmentPath(match, match->real_on_path[yj]))) {
    				match->real_on_path[yj] = xi;
    				return true;
    			}
    		}
    	}
    	return false;
    }
    void Clear_Supposed_On_Path_Sign(MAX_MATCH *match) {
    	for (int i = 0; i < UNIT_COUNT; i++) {
    		match->supposed_on_path[i] = false;
    	}
    }
    bool Hungry_Match(MAX_MATCH *match) {
    	for (int xi = 0; xi < UNIT_COUNT; xi++) {
    		if (FindAugmentPath(match, xi)) {
    			match->max_match++;
    		}
    		Clear_Supposed_On_Path_Sign(match);
    	}
    	return (match->max_match == UNIT_COUNT);
    }
    void InitGraph(MAX_MATCH *match, PARTNER *X, PARTNER *Y) {
    	match->max_match = 0;
    	memset(match->edge, 0, sizeof(int)*UNIT_COUNT*UNIT_COUNT);
    	for (int i = 0; i < UNIT_COUNT; i++) {
    		match->supposed_on_path[i] = false;
    		match->real_on_path[i] = -1;
    		for (int j = 0; j < X[i].pCount; j++) {
    			match->edge[i][X[i].perfect[j]] = 1;
    		}
    	}
    }
    void PrintResult(MAX_MATCH *match,PARTNER *X,PARTNER *Y) {
    	for (int i = 0; i < match->max_match; i++) {
    		cout << X[match->real_on_path[i]].name << "  与之相连的Y点是: " << Y[i].name << endl;
    	}
    }
    int main(){
    	MAX_MATCH match;
    	InitGraph(&match, X, Y);
    	if (Hungry_Match(&match)) {
    		PrintResult(&match, X, Y);
    	}
    	return 0;
    }
    /*
    问题描述:有一个二部图,图中的节点分属于两个节点集合,求他们的一个最大匹配,使用匈牙利算法求解二分图的最大匹配问题
    数据结构:首先使用PARTNER的数据结构存储一个节点的基本信息,比如节点名字,节点的边有多少条,这些边和另一个几何中的哪些点相连,
              求最大匹配的时候将这个节点与哪个节点匹配了的信息。然后使用两个节点的集合来描述二部图中所有节点和边的信息。
    		  再使用叫MAX_MATCH的数据结构来存储当前找到的最大匹配的信息,首先需要记录最大匹配中匹配对数的变量,需要存储边
    		  信息的结构(以便在假设相连的过程中进行判定),需要一个 supposed_on_path的数组来在递归时随着递归的深入将Y节点分配出
    		  去,需要一个real_on_path的数组在完成一次匹配时真正将Y节点与X节点匹配,所以real_on_path这个数组中存贮的其实是真正与
    		  对应下标Y节点相连的X节点的下标。这样所有数据的存储问题就解决了。
    算法描述:假设二分图中节点集合有X节点集合与Y节点集合两个集合,算法假设总是从X节点出发去寻找匹配,对于X节点集合中的
              **每一个**xi节点,通过edge[][]数组找在Y集合中和他**每一个**相连的yj节点,并从中选出一个yj,先假设将yj节点分配给
    		  当前xi节点,如果yj节点是自由节点,就把yj对应的real_on_path[]数组第j位设置为i,表示yj与xi相连。或者虽然当前的yj
    		  已经通过前面的分配与X集合中的某个节点相连了,但是如果将前面已匹配成功的(xi,yj)对的匹配关系通过冗余的边稍微做改
    		  变可以使它变成自由节点,就把yj对应的real_on_path[]数组第j位设置为i,表示yj与xi相连。每次完成一对匹配就将MAX_MATCH
    		  中的max_match变量加1,(通过当前算法找到一对匹配)如果最后max_match值等于二分图中所有节点数量的一半(这里假设给出
    		  的)图中两个集合中节点数量是相同的,就表明找到了一个完美匹配。(当最大匹配中没有剩余节点时,它将成为完美匹配)。
    */

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

    展开全文
  • 什么是数据结构与算法 数据结构 数据结构顾名思义,就是数据的结构(其实我觉得数据结构这四个字已经很形象了),也就是数据的存储结构或者存储方式,...我们知道,程序设计的目的就是模拟生活场景,那么首先就是将数据

    什么是数据结构与算法

    数据结构

    数据结构顾名思义,就是数据的结构(其实我觉得数据结构这四个字已经很形象了),也就是数据的存储结构或者存储方式,那么为什么会有数据结构呢,这是因为计算机中的数据都是用来描述我们实际生活中的各种场景的,而不同场景的数据特征就决定了数据的存储方式必然是多种多样的。例如水杯盛水这个场景中,水杯这个容器是单入口单出口,并且出入口相同;血管供血这个场景中,血管这个容器(没有分支的血管)也是单入口单出口,但是出入口不相同。

    算法

    我们知道,程序设计的目的就是模拟生活场景,那么首先就是将数据特征提取出来并利用数据结构存储,有了这些数据还要怎么办呢?没错肯定是进行计算了,或者说是对数据进行操作,那么这个过程就是所谓的算法,算法就是对数据的操作。

    数据结构与算法之间的关系(个人理解)

    那么究竟是数据结构决定算法,还是算法决定数据结构呢,还是两者相互独立呢,我的个人理解是数据结构决定算法,数据的存储方式决定了数据的操作方式。

    持续更新*

    展开全文
  • bsd的路由查找算法我研究过一段时间,当时我们要自己写一个路由查找模块,要扩展性好的,要紧凑...一个是LC-trie算法,我感觉linux设计的东西 不是那么紧凑,但绝对是一件艺术品,比较适合有品味的人欣赏和使用,大...
  • 1、动态规划算法的理解 (1)基本思想: 动态规划算法的基本思想与分治法类似:将待求解的问题分解成若干个子问题,先求解子问题,然后从这些子问题的解中得到原问题的解。但是,与分治法不同的是,为了避免重复...
  • 堆排序是利用堆这种数据结构而设计的一种排序算法,堆排序是一种选择排序,它的最坏,最好,平均时间复杂度均为O(nlogn),它也是不稳定排序。首先简单了解下堆结构。 堆 堆是具有以下性质的完全二叉树:每个结点的值...
  • Bresenham算法理解

    万次阅读 多人点赞 2017-12-24 17:48:49
    bresenham算法是计算机图形学中为了“显示器(屏幕或打印机)系由像素构成”这个特性而设计出来的算法,使得在求直线各点过程中全部以整数来运算,因而大幅度提升计算速度。 实现代码这篇文章主要下面代码...
  • 递归算法的理解

    2017-01-16 10:21:35
    递归算法是软件设计中解决递归问题思想。什么是递归。我们可以从字面意思去理解意思。递归递归,先递再归。递意思就是递推,即从高向下逐步展开。归意思就是回归,即从下向上进行。也就是说当你拿到了一个...
  • 这段时间因为工作需要,了解了一些聚类算法,发现目前国内一些资料中对于AP(Affinity Propagation)聚类算法的描述和理解局限在列举公式,说明计算流程层面,没有去深入解读,为什么要这样设计公式,以及AP...
  • 实验四 银行家算法的实现 1实验目的 通过编写和调试银行家算法的模拟程序以加深避免死锁方案的理解 熟悉银行家算法的分 配思想 2 实验要求 设计一个银行家方案并编写模拟程序实现之已知系统总共的资源数进程名 ...
  • 这篇文章总结了由Diego Ongaro和John Ousterhout所发表的论文《In Search of An ...它被设计的易于理解。用来解决多台服务器在共享状态上即使发生故障也能达成一致的问题。共享状态通常是一个通过复制日...
  • 本文基于UCAS卜东波老师的算法课撰写,包含了笔者自己快排思考,看完之后能快排有一个更深入了解
  • 目录   度量一个程序(算法)执行时间的两种...一是要想对设计的算法的运行性能进行评测,需要实际运行该程序; 二是所得时间的统计量依赖于计算机的硬件、软件等环境因素, 这种方式,要在同一台计算机的相同状态...
  • 动态规划算法的理解

    2019-08-22 22:50:10
    动态规划(dynamic programming)与分治方法类似,都是通过组合子问题解来... 通常按照一下四个步骤来设计一个动态规划算法: 刻画一个最优结构特征。 递归地定义最优解值。 计算最优解值,通常采用自...
  • 实验一 算法设计基础   一.实验目的 理解蛮力法思想及程序执行过程; 理解递推算法思想; 能较熟练地编写枚举、递推程序,给定问题能设计出相应算法予以解决。   二.实验基本步骤 1. 选定实验...
  •         以前写机器视觉算法时候,依赖从opencv中提取出...在线序检测算法设计中,在整张图片中截取了1个像素高度横向区域,得到1920个rgb像素点,转换为hsv颜色空间...
  • FFT算法研究报告 程序设计背景(FFT算法理解) FFT(fast fourier transformation,快速傅里叶变换是DFT算法的改进其利用了WNnk周期性共轭对称性和可约性使得DFT中有些项可以合并大大减小了计算量 按输入序列在时间...
  • 算法设计是一件非常困难工作,经常采用的算法设计技术主要有迭代法、穷举搜索法、递推法、贪婪法、回溯法、分治法、动态规划法等等。另外,为了更简洁形式设计和描述算法,在算法设计时又常常采用递归技术,用...
  • 考点梳理 例题剖析 第三部分 算法与VB程序设计 专题13 算法的表示流程图 考试内容 考试要求 算法算法的表示 算法的基本概念 算法的常用表示方法 顺序选择循环三种控制结构 b理解 本专题包含算法的表示其知识点主要...
  • 通过算法对数据进行操作就可以实现一些特定功能,多个功能组合起来就是一个应用程序,此时它也就具备了和人交互能力。 作为一个程序员,需要哪些功能并不是我们关心重点。这主要是产品设计层次问题,需要...
  • 实验项目 设p1=(x1,y1),p2=(x2,y2),…,...(2) 理解这样一个观点:分治与递归经常同时应用在算法设计之中。 实验要求 (1) 分别用蛮力法和分治法求解最近问题; (2) 分析算法时间性能,设计实验程...
  • 蒙哥马利算法理解

    千次阅读 2018-03-07 17:16:47
    我自己在看了网上的一些讲述蒙哥马利算法的资料之后总结了一下自己蒙哥马利算法的理解,因此在此分享出来。另外,我觉得要提醒大家的是在看该算法之前可以大概地看一下“求模”相关的运算,这样理解起来就可能会更...
  • 算法设计技巧与分析

    热门讨论 2016-04-26 21:49:18
    书中每章后都附有大量的练习题,有利于读者书中内容的理解和应用。, 《算法设计技巧与分析》结构简明,内容丰富,适合于作为计算机学科及相关学科算法课程的教材和参考书,尤其适宜于学过数据结构和离散数学课程...
  • Cristiano算法设计基础

    2020-09-07 09:15:31
    2、算法设计的主要任务是描述问题的解决方案 3、算法分析的主要任务是对算法进行比较 4、算法的核心是效率 5、计算机专业的基本学科能力归纳为计算思维能力、算法设计与分析能力、程序设计与实现能力、系统能力 二、...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,710
精华内容 1,484
关键字:

对算法设计的理解