为您找到搜索结果:1674个
【转】十大经典排序算法
转自十大经典排序算法:https://www.cnblogs.com/onepixel/articles/7674659.html 0、算法概述0.1算法分类十种常见排序算法可以分为两大类:比较类排序:通过比较来决定元素间的相对次序,由于其时间复杂度不能突破O(nlogn),因此也称为非线性时间比较类排序。非比较类排序:不通过比较来决定元素间的相对次序,它可以突破基于比较排序的时间下界,以线性时间运行,因此也称为线性时间非比较类排序。 0.2算法复杂度0.3相关概念稳定:如果a原本在b前面,而a=b,排序之后a仍然在b的前面。不稳定:如果a原本在b的前面,而a=b,排序之后a可能会出现在b的后面。时间复杂度:对排序数据的总的操作次数。反映当n变化时,操作次数呈现什么规律。空间复杂度:是指算法在计算机内执行时所需存储空间的度量,它也是数据规模n的函数。 1、冒泡排序(BubbleSort)冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列...
大津二值化算法自动确定二值化图像时的阈值
大津算法,也被称作最大类间方差法,是一种自动确定二值化阈值的算法。在这里作者不介绍算法推导的过程,算法推导过程网络上有许多介绍,这里只给出算法最终推导出的结论:使得左侧 的值最大,就可以得到最好的二值化阈值t其中,和 是被阈值分开的两个类中的像素数占总像素数的比率。和 分别是这两个类的像素值的平均值。废话不多说,直接上python代码:importcv2importnumpyasnpdefBGR2GRAY(img): b=img[:,:,0].copy() g=img[:,:,1].copy() r=img[:,:,2].copy() #Grayscale out=0.2126*r+0.7152*g+0.0722*b out=out.astype(np.uint8) returnout#OtsuBinarizationdefotsu_binarization(img,th=128): max_sigma=0 max_t=0 #determinethreshold for_tinrange(1,255): v0=out[np.wh...
递推算法
递推算法是一种简单的算法,即通过已知条件,利用特定关系得出中间推论,直至得到结果的算法。递推算法分为顺推和逆推两种。递推与递归的比较相对于递归算法,递推算法免除了数据进出栈的过程,也就是说,不需要函数不断的向边界值靠拢,而直接从边界出发,直到求出函数值.比如阶乘函数:f(n)=n*f(n-1)在f(3)的运算过程中,递归的数据流动过程如下:f(3){f(i)=f(i-1)*i}-->f(2)-->f(1)-->f(0){f(0)=1}-->f(1)-->f(2)--f(3){f(3)=6}而递推如下:f(0)-->f(1)-->f(2)-->f(3)由此可见,递推的效率要高一些,在可能的情况下应尽量使用递推.但是递归作为比较基础的算法,它的作用不能忽视.所以,在把握这两种算法的时候应该特别注意。顺推法所谓顺推法是从已知条件出发,逐步推算出要解决的问题的方法叫顺推。如斐波拉契数列,设它的函数为f(n),已知f(1)=1,f(2)=1;f(n)=f(n-2)+f(n-1)(n>=3,n∈N)。则我们通过顺推可以知道,f(3)=...
数据结构和算法
数据结构:数据之间存在某种关系;算法:对问题求解的步骤描述,在计算机中表现为一些列指令和操作算法五个特性:输入(输入参数),输出(得到的结果),确定性(步骤是有意义的无歧义的),可行性(每个步骤都是可行的)正确性(除前面的特性外,还还具有反映出问题的需求并得到正确的答案) 算法效率度量:事后计算:测试方法和算法要一对一;事前估算:时间复杂度(执行的次数),空间复杂度...
如何用Go语言实现汉诺塔算法
packagemainimport("fmt")funcprint(nint,xrune,yrune)(){fmt.Printf("movingdisk%dfrompole%ctopole%c",n,x,y)}funcmove(nint,arune,brune,crune)(){ifn==1{print(n,a,c)}else{move(n-1,a,c,b);print(n,a,c);move(n-1,b,a,c)}}funcmain(){varnint;fmt.Println("Pleaseinputthedisknumbern:");fmt.Scanf("%d",&n);move(n,'x','y','z')} ...
计算机科学中最重要的32个算法
http://www.infoq.com/cn/news/2012/08/32-most-important-algorithms?utm_source=infoq&utm_medium=popular_links_homepagehttp://www.risc.jku.at/people/ckoutsch/stuff/e_algorithms.html 奥地利符号计算研究所(ResearchInstituteforSymbolicComputation,简称RISC)的ChristophKoutschan博士在自己的页面上发布了一篇文章,提到他做了一个调查,参与者大多数是计算机科学家,他请这些科学家投票选出最重要的算法,以下是这次调查的结果,按照英文名称字母顺序排序。A*搜索算法——图形搜索算法,从给定起点到给定终点计算出路径。其中使用了一种启发式的估算,为每个节点估算通过该节点的最佳路径,并以之为各个地点排定次序。算法以得到的次序访问这些节点。因此,A*搜索算法是最佳优先搜索的范例。集束搜索(又名定向搜索,BeamSearch)&mdash...
水仙花算法
打印出所有的"水仙花数",所谓"水仙花数"是指一个三位数,其各位数字立方和等于该数本身。例如:153是一个"水仙花数",因为153=1的三次方+5的三次方+3的三次方。 /*打印出所有的"水仙花数",所谓"水仙花数"是指一个三位数,其各位数字立方和等于该数本身。例如:153是一个"水仙花数",因为153=1的三次方+5的三次方+3的三次方。*/publicclassArithmetic_daffodil{publicstaticvoidmain(String[]args){for(inti=100;i<=999;i++){if(isDaffodial(i)){System.out.println(i);}}}publicstaticbooleanisDaffodial(intnum){intsingle=num%10;intten=(num/10)%10;inthundred=(num/100)%10;/*System.out.println(num);System.out.println(single);System.out.println(ten);System.o...
基础算法-兔子繁殖
古典问题:有一对兔子,从出生后第3个月起每个月都生一对兔子,小兔子长到第四个月后每个月又生一对兔子,假如兔子都不死,问每个月的兔子总数为多少?升级版(输入一个兔子的数量,问最少多少个月可以达到?)程序分析:兔子的规律为数列1,1,2,3,5,8,13,21....也就是说当月兔子的数量=上月个兔子的数量+当月出生量(即三个月前的数量)publicclassArithmetic_rabbit{publicstaticvoidmain(String[]args){intindex=10;if(args!=null&&args.length>0){index=Integer.parseInt(args[0]);}//从第一个月开始inti=1;while(getNum(i)<index){i++;}System.out.println(index+"只兔子,至少需要"+i+"个月");/*查看每个月兔子的数量for(inti=1;i<=index;i++){System.out.println("第"+i+"个月,有"+getNum(i));}*/}//递归...
水平集与图割算法浅析
LeveSet水平集方法主要的思想是利用三维(高维)曲面的演化来表示二维曲线的演化过程。在计算机视觉领域,利用水平集方法可以实现很好的图像分割效果。1.数学原理根据维基百科的定义,在数学上一个包含n个变量的实值函数其水平集可以表示为下面的公式:Lc(f)=(x1,x2,...,xn)∣f(x1,x2,...,xn)=cL_c(f)={(x_1,x_2,...,x_n)|f(x_1,x_2,...,x_n)=c}Lc(f)=(x1,x2,...,xn)∣f(x1,x2,...,xn)=c可以看出,水平集指的是这个函数的取值为一个给定的常数c.那么当变量个数为2时,这个函数的水平集就变味了一条曲线,也可以成为等高线。这时函数f就可以描述一个曲面。(同样,三个变量时就能得到一个等值面,大于3的就是水平超面了)下面来看一个简单的曲面的水平集(等值线的例子):上图中,左边是Himmelblau方程所描述的曲面即z=f(x,y)z=f(x,y)z=f(x,y),右边就是这个曲面的等高线集合,其中每一条就对应着一个常数c的水平集。2.水平集方法在计算机视觉中,利用水平集方法的优势在于,...
数据结构——排序算法总结
排序(Sorting)就是将一组对象依照规定的次序又一次排列的过程,排序往往是为检索而服务的。它是数据处理中一种非常重要也非经常常使用的运算。比如我们日常学习中的查字典或者书籍的文件夹。这些都事先为我们排好序,因此大大减少了我们的检索时间,提高工作效率。 排序可分为两大类: 内部排序(InternalSorting):待排序的记录所有存放在计算机内存中进行的排序过程; 外部排序(ExternalSorting):待排序的记录数量非常大,内存不能存储所有记录。须要对外存进行訪问的排序过程。 外部排序自己现阶段还没有接触和学习。因此这里我们仅仅研究内部排序的集中算法。希望能和大家互相学习共同进步。 内部排序的中比較常见的有四种算法,以下我们分别对各种算法常见的算法进行学习。思维导图例如以下: 基本思想:在一个已经排好序的序列中,将未被排序的元素依照原先序列的排序规则插入到序列中的指定位置。 经常使用举例:直接插入排序 ...
[算法天天练]堆排序
#include<iostream>#include<algorithm>usingnamespacestd;voidHeapAdjust(int*a,inti,intsize)//调整堆{intlchild=2*i;//i的左孩子节点序号intrchild=2*i+1;//i的右孩子节点序号intmax=i;//临时变量if(i<=size/2)//如果i是叶节点就不用进行调整{if(lchild<=size&&a[lchild]>a[max]){max=lchild;}if(rchild<=size&&a[rchild]>a[max]){max=rchild;}if(max!=i){swap(a[i],a[max]);HeapAdjust(a,max,size);//避免调整之后以max为父节点的子树不是堆}}}voidBuildHeap(int*a,intsize)//建立堆{inti;for(i=size/2;i>=1;i--)//非叶节点最大序号值为size/2{HeapAdjust(...
[转][算法天天练]堆与堆排序
堆排序与快速排序,归并排序一样都是时间复杂度为O(N*logN)的几种常见排序方法。学习堆排序前,先讲解下什么是数据结构中的二叉堆。二叉堆的定义二叉堆是完全二叉树或者是近似完全二叉树。二叉堆满足二个特性:1.父结点的键值总是大于或等于(小于或等于)任何一个子节点的键值。2.每个结点的左子树和右子树都是一个二叉堆(都是最大堆或最小堆)。当父结点的键值总是大于或等于任何一个子节点的键值时为最大堆。当父结点的键值总是小于或等于任何一个子节点的键值时为最小堆。下图展示一个最小堆:由于其它几种堆(二项式堆,斐波纳契堆等)用的较少,一般将二叉堆就简称为堆。一般都用数组来表示堆,i结点的父结点下标就为(i–1)/2。它的左右子结点下标分别为2*i+1和2*i+2。如第0个结点左右子结点下标分别为1和2。 下面先给出《数据结构C++语言描述》中最小堆的建立插入删除的图解,再给出本人的实现代码,最好是先看明白图后再去看代码。 堆的插入每次插入都是将新数据放在数组最后。可以发现从这个新数据的父结点到根结点必然为一个有序的数列,现在的任务是将这个新数据插入到这个有序数据中&m...
[算法天天练]选择排序法
#include<stdio.h>voidshow(intarr[],intlength){for(inti=0;i<length;i++){printf("%d",arr[i]);}printf("");}void_swap(int*a,int*b){inttmp=*a;*a=*b;*b=tmp;}voidSelectSort(intarr[],intlength){size_ti,j;intmin;for(i=0;i<length-1;i++){//假设arr[i]为最小的数min=arr[i];//通过循环获取数组中剩余数中的最小数for(j=i+1;j<length;j++){if(min>arr[j]){_swap(&min,&arr[j]);}}//将最小的数放到正确的位置if(arr[i]!=min){_swap(&arr[i],&min);}}}intmain(){intarr[10]={2,1,5,4,3,9,8,7,6,0};SelectSort(arr,10);show(arr,10);retur...
[算法天天练]插入排序算法
#include<stdio.h>voidshow(intarr[],intlength){for(inti=0;i<length;i++){printf("%d",arr[i]);}printf("");}voids_insert(intarr[],intlength){if(length<0)return;for(inti=1;i<length;i++){intk=i;for(intj=0;j<i;j++){if(arr[j]<arr[k]){intt=arr[j];arr[j]=arr[k];arr[k]=t;}}}}intmain(){intarr[10]={2,1,5,4,3,9,8,7,6,0};s_insert(arr,10);show(arr,10);return0;} ...
[算法天天练] 归并排序
要实现归并排序递归方法:第一步:先将原来的数据表分成排好序的子表,然后调用合并函数对子表进行归并,使之成为有序表例如有如下向量:⑴⑵⑶⑷⑸⑹⑺⑻⑼⑽⑾25,10,7,19,3,48,12,17,56,30,21/25,10,7,19,348,12,17,56,30,21//25,107,19,348,12,1756,30,21////2510719,3............ 归并算法划分子表和归并子表与原数据序列次序无关,因此算法最坏情况,最坏情况和平均情况时间复杂度是一样的,时间复杂度为O(NlogN),空间复杂度O(N+logN)#include<stdio.h>#include<stdlib.h>voidMerge(intarr[],intbeg,intmid,intend){inti=beg;intj=mid+1;intp=0;int*ipa;ipa=(int*)malloc((end-beg+1)*sizeof(int));if(!ipa)return;while(i<=mid&&j<=end){//ipa[p+...