精华内容
下载资源
问答
  • 一个算法的优劣可以用空间复杂度时间复杂度来衡量。 2,特征 1>有穷性(Finiteness):指的是算法必须在执行有限个步骤之后能够终止,简单的理解,就是程序需要一个终止的标识,不然程序可能就会陷入死循环的...

    算法

    1,概念

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

    2,特征

    1>有穷性(Finiteness):指的是算法必须在执行有限个步骤之后能够终止,简单的理解,就是程序需要一个终止的标识,不然程序可能就会陷入死循环的状态。

    2>确切性(Definiteness):每一步必须有确定的定义。

    3>输入项(Input):有0个或者多个输入,给予运算对象的一个初始状态,所谓0个输入是指算法本身定出了初始条件。

    4>输出项(Output):有1个或者多个输出,反映输入的数据被程序加工后的结果,没有输出的算法是没有意义的。

    5>可行性(Effectiveness):算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步骤,即每个计算步骤都可以在有限时间内完成(也称之为有效性)。

    3,评定

    同一个问题可以用不同的算法解决,一个算法的质量好坏影响到这个算法和程序的执行效率,一个算法的评价主要从时间复杂度和空间复杂度来考虑。

    3.1 时间复杂度

    时间复杂度是指执行算法所需要的计算工作量。一般来说,算法的时间复杂度记做:T(n)=Ο(f(n))
    因此,问题规模n 的值越大,算法执行的时间的增长率与f(n) 的增长率正相关,称作渐进时间复杂度(Asymptotic Time Complexity)。

    按数量级递增排列,常见的时间复杂度有:

    常数阶O(1),对数阶O(log2n),线性阶O(n),线性对数阶O(nlog2n),平方阶O(n^2), 立方阶(n^3),…, 指数阶O(2^n)。随着问题规模n的不断增大,上述时间复杂度不断增大,算法的执行效率越低

    以上六种计算算法时间的多项式是最常用的。其关系为:
    O(1)<O(logn)<O(n)<O(nlogn) <O(n2)<O(n3)

    指数时间的关系为:O(2n)<O(n!)<O(n^2)
    当n取得很大时,指数时间算法和多项式时间算法在所需时间上非常悬殊。

    3.2 空间复杂度

    空间复杂度是指算法需要消耗的内存空间,其计算和表示方法与时间复杂度相似,同时间复杂度相比,空间复杂度的分析要简单一些。一般记作:记做S(n)=O(f(n))

    二者的关系:对于一个算法,时间复杂度和空间复杂度往往是相互影响的。当想要一个较好的时间复杂度时,可能会使空间复杂度的性能变差,即可能导致占用较多的存储空间;反之,当想要一个较好的空间复杂度时,可能会使时间复杂度的性能变差,即可能导致占用较长的运行时间

    4,方法

    4.1 递归法

    程序调用自身的方法技巧称为递归(recursion)。一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法,递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量。一般来说,递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时,递归前进;当边界条件满足时,递归返回。

    注意:1)递归就是在过程或函数里调用自身;
    2)在使用递归策略时,必须有一个明确的递归结束条件,称为递归出口。

    例题:利用递归实现斐波那契数列,斐波那契数列规律为1,1,2,3,5,8,13,21,…
    在这里插入图片描述

    4.2 穷举法

    是一种最简单的算法,来穷尽出现的问题每一种可能的情况,从而解决问题。简单地说,利用循环把各种可能出现的情况都走一遍,把满足要求的结果筛选出来。

    适用的场景:穷举的效率不高,用于没有明显规律的情况。

    例题:韩信点兵问题,韩信知道部队人数大约1000人左右,具体数字不详,5人一组剩余1人,7个人一组还剩两个人,8个人一组还剩3个人,问:这支部队有多少人?

    在这里插入图片描述

    4.3 冒泡排序

    一种简单直观的排序算法,重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端。

    思想:比较相邻的元素。如果前一个比后一个大,就交换他们两个的位置,对每一对相邻元素作同样的工作,第一轮之后,最大的数会在最后,就这样从第一对开始到结尾的最后一对,重复以上的步骤,执行的次数会越来越少,直到没有任何一对数字需要比较。

    例题:对一组数字利用冒泡的方法进行排序,结果从小到大

    在这里插入图片描述
    在这里插入图片描述

    5,算法的复杂度

    在这里插入图片描述

    扩展

    练习题:有5个人坐在一起,问第五个人多少岁?他说比第4个人大2岁。问第4个人岁数,他说比第3个人大2岁。问第三个人,又说比第2人大两岁。问第2个人,说比第一个人大两岁。最后问第一个人,他说是10岁。请问第五个人多大?
    在这里插入图片描述

    展开全文
  • 冒泡算法的时间复杂度问题

    千次阅读 2014-11-30 16:57:16
    最近在学习算法过程中发现了一个小... 在许多地方看到冒泡排序的最佳时间复杂度为O(n),于是自己写了个冒泡排序如下:  public void bubbleSort(int[] a){ for(int i=1;i;i++){ for(int j=0;j;j++){ if(a[j]>a

      最近在学习算法过程中发现了一个小问题,在这里和大家分享一下。

      在许多地方看到冒泡排序的最佳时间复杂度为O(n)于是自己写了个冒泡排序如下:

     

    <span style="font-size:18px;">public void bubbleSort(int[] a){
        for(int i=1;i<a.length;i++){
           for(int j=0;j<a.length-i;j++){
              if(a[j]>a[j+1]){
                        int temp=a[j];
                        a[j]=a[j+1];
                        a[j+1]=temp;
               }
            }
       }
    }
    </span>

      看了半天自己的代码,即使是正序排列,就算第一趟排序没有交换,比较操作循环还是会继续,次数为n*(n-1)/2之,怎么会出现O(n)的复杂度呢?




      后来在网上查了一下,原来是我的代码有问题,可以继续优化。如果按照我的思路,即使最好的情况复杂度还是O(n2),因为比较循环会一直进行下去直到循环结束。

    优化方法应该设置一个中断标志位,在条件测试中如果发生了交换就将中断位屏蔽,然后在外层循环中检查中断位,如果中断位没有被屏蔽,将结束循环。每次开始内层循环之前重置中断位。这样就可以在已经是正序排列时不继续进行循环,达到最优的复杂度。优化代码如下:

    <span style="font-size:18px;">public void bubbleSort(int[] a){
    
       for(int i=1;i<a.length;i++){
               boolean didSwap=false;
                   for(int j=0;j<a.length-i;j++){
                      if(a[j]>a[j+1]){
                            int temp=a[j];
                            a[j]=a[j+1];
                            a[j+1]=temp;
                            didSwap=true;
                       }
                   }
               if(!didSwap)   return;
        }
    }</span>



     
    

    展开全文
  • 最近,笔者学习了冒泡排序,在此简单分享一下。 冒泡排序的原理:  对于一个数组,冒泡排序算法会比较相邻的两项的大小,并进行交换。  对每一对相邻的元素做同样的调整,如:第一个和第二个,第二个和第三个,...

    最近,笔者学习了冒泡排序,在此简单分享一下。

    冒泡排序的原理:
            对于一个数组,冒泡排序算法会比较相邻的两项的大小,并进行交换。

            对每一对相邻的元素做同样的调整,如:第一个和第二个,第二个和第三个,第三个和第四个等等,以此类推。这样下来,最后的元素会是最大的。

            重复以上步骤。如果有n个元素,则第一次循环进行n-1次,第二次循环进行n-2次,…………,第n-j次循环过后,会按大小顺序排出j个较大的数。

            持续以上的步骤,直到没有任何一堆数字需要比较。

    冒泡原理的简单应用:
            任务:排序:4,9,10,5,7



    时间复杂度与空间复杂度

            时间复杂度:时间复杂度是一个函数,定量描述了算法的运算时间,用大O符号来表示。在计算的时候,先找出算法基本操作的执行次数,即为T(n),然后找到它的同数量级,即为f(n),如果T(n)与f(n)的比值求极限可得到一个常数c,那么时间复杂度T(n)=O(f(n))。

           上面的冒泡排序的时间复杂度计算(计算下方的for循环):T(n) = (4n+1)n,f(n) = n*n,c = 4,则时间复杂度为:T(n) = O(n*n)

           空间复杂度:空间复杂度是运行完一个程序所需要的内存的大小。这里包括了存储算法本身所需要的空间,输入与输出数据所占空间,以及一些临时变量(比如上面的h)所占用的空间。一般而言,我们只比较额外空间,来比较算法的空间优越性。

           上面的冒泡排序的临时变量所占空间不随处理数据n的大小改变而改变,则空间复杂度为O(1)。


    优化冒泡排序:

            如果给出的数据为1,2,3,4,5,6,7,9,8,要求进行排序,那么只需要进行一次交换即可。但此时程序仍然会继续检测到1为止。此时需要进行优化。




    以上如果有表述不当之处,还请指出更正!

                                                                         2017-8-20   上午































































    折叠

    展开全文
  • 在我们写一些简单的程序中,对一组数据进行简单的有序的排列...而冒泡排序就是我们学习排序的基础 冒泡排序: 形象的可以理解为:水中上升的气泡,在上升的过程中,气泡越来越小,不断比较相邻的元素,将小的往后调


    在我们写一些简单的程序中,对一组数据进行简单的有序的排列是经常会遇到的,所以我们必须熟悉几种基本的算法。

    而冒泡排序就是我们学习排序的基础


    冒泡排序:

    形象的可以理解为:水中上升的气泡,在上升的过程中,气泡越来越小,不断比较相邻的元素,将小的往后调


    我们来解决这样一个问题:

    设有一数组,其大小为6个元素(int array[6]),数组内的数据是(4,2,5,3,2,6),此刻数据是无序的,现要求我们编程将其变成一个有序的从大到小的数组,从下标0开始。


    思考:按照题目要求,毫无疑问,最终的有序数组应该是这样(6,5,4,3,2,2),要做到这样,最简单的办法就是进行比较交换


    1:我们从数组的第一个元素array[0]向后走,如果比相邻的小,那么交换,如此进行下去,可以发现,我们找到了所

          有元素中最小的并且已经将它放在了最后一个位置array[5]

    2:然后,我们重新从第一个元素向后走,还是相邻的比较,并且交换,但是我们只需要比较到4,放在array[4]

    3:重复第二步,直到比较到1


    代码:

    #include <stdio.h>
    #include <iostream>
    using namespace std;
    
    void Bubble_sort(int *array, int length)
    {
            //变量i,j用于循环,变量t用于交换中间值
            int i, j, t;
            for(i = 1; i < length; i++)
            {       
                    //比较的次数越来越少,但是每一个都能在相应的范围内确定一个最小值并放在合理的位置
                    for(j = 0; j < length - i ; j++)
                    {
                            //在满足条件的情况下,交换两个数
                            if(array[j] < array[j + 1])
                            {
                                    t = array[j];
                                    array[j] = array[j + 1];
                                    array[j + 1] = t;
                            }
                    }
            }
            //将6个数输出
            for(i = 0; i< length; i++)
                    cout<<array[i]<<endl;
    }
    
    int main()
    {
            int array[] = {4,2,5,3,2,6};        //定义一个数组并简单的初始化
            int length = sizeof(array)/sizeof(int);//求定义数组的具体长度
            Bubble_sort(array, length);     //调用相应的排序函数
            
            return 0;       
    }

    关于优化:我们必须从时间复杂度和空间复杂度上面来看

    好多人一直都在纠结冒泡排序的时间复杂度

    在最坏的情况下是:O(N)

    还是在最坏的情况下是比较比较次数是:n(n - 1)/ 2

    他们两到底是什么关系???


    其实:总而言之,冒泡排序是一种用时间在换空间的排序。

    最坏的情况当然是:每一次的比较都会进行交换,也就是说要把逆序的数列变成顺序或者要把顺序变成逆序

    5,4,3,2,1以冒泡升序排列

    1,从第一个数5开始和后面的数进行比较比较到倒数第二个数2为止,过程为:5跟4比较,5比4大,两者交换,然后

          跟3比较,5比3大,继续进行交换,依次进行比较,比较完成为:4,3,2,1,5

    2,从第一个数4开始和后面的数进行比较,过程为:4跟3比较,4比3大,两者进行交换,然后跟2进行比较,4比2大

          ,继续交换,依次比较,比较完成为:3,2,1,4,5

    3,同理


    所以总的比较次数就是:4 + 3 + 2 + 1

    所以,对于n位数的比较次数就是:n + (n - 1)+(n -2)+...+1 = n(n - 1)/ 2


    而O(N^2)表示的是复杂度的数量级,举个例子来说,如果n = 10000,那么n(n -1 )/2 = (n^2 - n)/ 2

    = (100000000 - 10000)/2,相对于10^8来说,10000可以忽略不计,所以总计算次数约为0.5 * N^2.

    所以,就用O(N^2)表示了数量级(忽略了前面的系数0.5)



    所以,我们可以从趟数上面处理,因为有可能我们比较一定的倘数之后就已经变成了有序的了,没有必要再去做一些无用的比较了

    如:5,1,2,3,4

    冒泡一次之后就变成了:1,2,3,4,5已经有序了,我们没有必要再去比较了


    程序:

    #include <stdio.h>
    #include <iostream>
    using namespace std;
    
    void Bubble_sort(int *array, int length)
    {
            int i, j, t;
            int flag;                    //标志量,用于指示,数列已然是有序的
            for(i = 1; i < length; i++)
            {       
                    flag = 1;
                    for(j = 0; j < length - i ; j++)
                    {
                            if(array[j] < array[j + 1])   //合理的交换相邻的两个数
                            {
                                    flag = 0;
                                    t = array[j];
                                    array[j] = array[j + 1];
                                    array[j + 1] = t;
                            }
                    }
                    if(flag == 1)         //标志位
                            break;
            }
            
            for(i = 0; i< length; i++)//输出排序后的数列
                    cout<<array[i]<<endl;
    }
    
    int main()
    {
            int array[] = {4,2,5,3,2,6};
            int length = sizeof(array)/sizeof(int);
            Bubble_sort(array, length);
            
            return 0;       
    }

    这里我们加入了标志,flag,如果有一趟排序中没有产生交换的话,那么说明此刻数列以及变成了有序的数列



    从上面时间复杂度看,时间主要花费在交换上面了,如果转汇编的话,比较可能只需要一条指令,而交换可能就需要很多指令,所以我们的目的就是减少某一倘的交换次数即可

    如下:为了便于讲解,我们将上面用于排序的那些数列简单的改改

    4,2,3,2,6,7,8

    主要的就是:4,3,2,2(前面的排列),后面就是比较就是:

    array[3]跟array[4]比较,2小于6,那么记录下来,继续比较array[3]和array[5],2小于7,继续比较array[3]和array[6],

    2小于8,但是由于8是数列的最后一个所以我们直接交换:

    所以,第一次排序的结果就是:4,3,2,8,6,7,2

    可以简单的理解:

    就变成这样了,,,,(理解如上)


    #include <stdio.h>                                                                                                                    
    #include <iostream>
    using namespace std;
    
    void Bubble_sort(int *array, int length)
    {
            int i, j, t, k;
            int flag;       //flag表示减少的倘数
            for(i = 1; i < length; i++)
            {
                    flag = 1;
                    for(j = 0; j < length - i ; j++)
                    {
                            if(array[j] < array[j + 1])   
                            {
                                    flag = 0;
                                    k = j+ 1;
                                    while(k < length - i + 1)//确定其有效性
                                    {
                                            if(array[j] >= array[k]) //这里添加等号,是为了不影响程序的稳定性
                                            {
                                                    //交换array[j]与array[k - 1]
                                                    t = array[j];
                                                    array[j] = array[k - 1];
                                                    array[k - 1] = t;
                                                    break;
                                            }
                                            if(k == length - i)  //如果走到最后了,那么直接进行交换
                                            {
                                                    t = array[j];
                                                    array[j] = array[k];
                                                    array[k] = t;
                                                    break;
                                            }
                                            k++;
                                    }
                                    if(k == length - i)        //已经到了末尾了,可以直接退出本次的循环了
                                            break;
                                    k = k - 2;
                                    j = k;
                            }
                    } 
                    if(flag == 1)
                            break;
            }
            //输出我们排       
            for(i = 0; i< length; i++)
                    cout<<array[i]<<endl;
    }   
    
    int main()
    {
            //定义一个数组,并给其一个简单的初始化
            int array[] = {4,2,3,2,6,7,8};
            //求出数组的大小
            int length = sizeof(array)/sizeof(int);
            //调用排序函数
            Bubble_sort(array, length);
            
            return 0;       
    }
    
    
    
    



    如上程序:上面的k值就是类似与一个简单的标志



    关于第三步的优化方式,可能一部分人不太认同,因为对于冒泡而言,必须是跟相邻的进行比较,然后进行交换,而我上面这个不完全是这样的,但是,我还是认为,对于程序,重要的是:

    时间复杂度,空间复杂度,如果我们能针对当前的数列选择一个合理的排序方式,那就是极好的!!!

    因为,不同的排序,块排,插入,基数,堆排都有自己最适合的情况,我们不能要求某一个排序必须用某一个排序,是吧,,,,

    鄙人的一点简单看法,,谢谢大家指点,,,小子谢谢啦!!!






    展开全文
  • 冒泡排序算法是所有排序算法中最简单的(前面也提到过),在生活中应该也会看到气泡从水里面出来时,越到水面上气泡就会变的越大。在物理上学气压的时候好像也看到过这种现象;其实理解冒泡排序就可以根据这种现象来...
  • 时间复杂度是学习算法的基石,今天我们来聊聊为什么要引入时间复杂度,什么是时间复杂度以及如何去算一个算法的时间复杂度 一、刻画算法的运行时间 某日,慧能叫来了一尘打算给他补习补习一下基础知识,只见克写了...
  • 各种排序算法的稳定性,时间复杂度和空间复杂度总结:我们比较时间复杂度函数的情况:时间复杂度函数O(n)的增长情况:所以对于n较大的排序记,一般的选择都是时间复杂度为O(nlog2n)的排序方法。时间复杂度来说:1....
  • 时间复杂度及空间复杂度直白理解/快排/冒泡 常常在算法类的文章里看到时间复杂度,空间复杂度的名词,但是对其中的意思不是很清楚,但是大概是知道,复杂度代表了一个算法的运行效率,复杂度越大说明这个算法运行效率越...
  • 的弱上界是n^n,因此增长速度非常快,这意味着单位时间内可求解的问题很小,换言之,超慢 2^n这样的指数函数增长非常快,这种算法可以认为超慢 O(n^) 和O(n^3) 增长很快,算法很慢,至少优化到nlgn, O (n^2) 的有...
  • 时间复杂度

    2019-05-21 14:25:10
    O(n)不是算法,它是一个函数,是一个表征算法时间复杂度的一个函数。 计算机科学中,算法的时间复杂度是一个函数,它定性描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数时间复杂度常用...
  • 理解时间复杂度,插入排序,冒泡排序,选择排序 什么是时间复杂度 就是近似于约等于算法总的执行的次数; 说白了时间复杂度就是近似约等于算法中常数操作的次数; 时间复杂度使用O(n)(可以读big O n)来表示 在一个...
  • 这里主要涉及到时间复杂度、空间复杂度还有稳定性的问题 时间复杂度冒泡法为例,冒泡法排序的最坏情况就是每组数据都要交换一次,即:[5,4,3,2,1]变成[1,2,3,4,5]。那么在这个过程里,第一次外循环,“5”被交换...
  • 时间复杂度和空间复杂度

    多人点赞 2021-08-29 20:40:29
    在计算机科学中,时间复杂性,又称时间复杂度,算法的时间复杂度是一个函数,它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数时间复杂度常用大O符号表述,不包括这个函数的低阶项和首项...
  • 在计算机科学中,算法的时间复杂度是一个函数,它定量的描述了该算法的运行时间. 通俗的讲,一个算法所花费的时间与其中语句的执行次数成正比,算法中的基本操作的执行次数,为算法的时间复杂度 三. 时间...
  • 时间复杂度和空间复杂度 费波纳茨数列 二分查找 时间复杂度和空间复杂度 时间复杂度空间复杂度 斐波那契数列 递归版本非递归版本 冒泡排序折半查找 递归版本非递归版本 ...
  • 算法复杂度分为时间复杂度和空间复杂度时间复杂度用于度量算法执行的时间长短;而空间复杂度则是用于度量算法所需存储空间的大小。 目录 时间复杂度 1.时间频度 2.计算方法 3.分类 空间复杂度 算法的时间...
  • 时间效率被称为时间复杂度、空间效率被称为空间复杂度; 早期计算机发展储存量小,对看空间复杂度比较重视,现在存储容量不成问题,所以要注重时间复杂度。 一、时间复杂度 算法中基本操作的执行次数称为算法的...
  • 四大排序的时间复杂度和空间复杂度时间复杂度时间复杂度的表示方法时间复杂度的分析和计算方法常见的几种时间复杂度常见的时间复杂度排序空间复杂度 时间复杂度 (1)时间频率 一个算法执行所耗费的时间,从理论上是不...
  • 时间复杂度 算法效率时间复杂度评估算法运行时间大O渐进表示法最好/最坏/平均时间复杂度实例:计算耗时 算法效率 算法效率分为两种:第一种是时间效率,第二种是空间效率。 时间效率被称为时间复杂度,空间效率被...
  • 内容包括两种排序的原理,代码剖析,以及时间复杂度分析。因为注意到很多快排的文章在介绍完原理之后并没有去解释这么做的原因,以及没有从宏观上去看代码所实现的功能,也就是没有很详细的说明这么写代码的原因,看...
  • 常用的算法的时间复杂度和空间复杂度 排序法 最差时间分析 平均时间复杂度 稳定度 空间复杂度 冒泡排序
  • 时间复杂度 归并排序的时间主要花在了划分序列和合并序列上,由于是采用递归的方式进行合并,所以与快速排序类似,树的每层元元素的个数最多是n,也就代表着每层最多进行n次比较,而递归树最多只有log2n层,而且...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 28,973
精华内容 11,589
关键字:

冒泡函数时间复杂度