王彪20162321 2017-2018程序设计与数据结构-第二学期-第一周学习总结

时间:2021-10-02 10:34:21

第十二章-算法分析

1.1基础总结

  • 算法分析是计算机科学的基础课题。
  • 增长函数显示了与问题大小相关的时间或空间利用率。
  • 算法的阶有算法增长函数的主项决定。
  • 算法的阶给出乐算法增长函数的上界。
  • 更快的处理器不能弥补当问题的大小增长时算法的的效率。
  • 分析算大的复杂度时经常需要分析循环的执行情况。
  • 嵌套循环的分析必须要考虑内层和外层循环的执行情况。

1.2到底啥子是算法?

  1. 简单来说,算法就是一系列被控制的步骤,你通过按序执行这些步骤可以实现一些目标或者产生一些输出。
  2. 就好比在Windows上打开一个软件的方法步骤(这应该可以算作一个算法吧...)
puclic void 开软件1(){
    "
    1.找到桌面快捷方式
    2.双击鼠标左键
    "
}
public void 开软件2(){
    "
    1.打开我的电脑
    2.在电脑硬盘中找到安装目录
    3.在安装路径中找的软件的主程序模块
    4.单击鼠标右键
    5.在弹出的菜单中选择"打开"
    
    "
  
}

3.就犹如你可以有很多种打开一个软件的方式一样,你可以用多种不同的算法来解决同一个问题。打开方式的麻烦程度就好比解决这问题的效率。有的解决办法效率更高,比其他方法需要更少的时间和空间。问题是如何分析那个算法效率高。

2.1算法分析

  • 算法是解决问题的方法,一个问题可以有多种解决方法,不同的算法之间就有了优劣之分。如何对算法进行比较呢?算法可以比较的方面很多,如易读性、健壮性、可扩展性等,但不是最关键的方面,算法的核心和灵魂是效率,也就是解决问题的速度。试想,一个需要运行很多年才能给出正确结果的算法,就是其他方面的性能再好,也是一个不实用的算法。(引用网络)

判断算法性能的一个基本考虑是处理一定“规模”的输入时该算法所需要执行的“基本操作”数。“规模”一般指输入量的数目。一个“基本操作”必须具备这样的性质:完成该操作所需时间和操作数的具体取值无关。

2.2时间复杂度

  • 算法的时间复杂度被设计来评价其语句执行次数。但它又不是语句执行次数,而是次数的同数量级函数。

  • 一个算法执行所耗费的时间,从理论上是不能算出来的,一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多。

  • 一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),使得当n趋近于无穷大时,T(n)/f(n)的极限值为不等于零的常数,则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度,简称时间复杂度。时间频度不同,但时间复杂度可能相同。如:T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同,但时间复杂度相同,都为O(n2)。按数量级递增排列,常见的时间复杂度有:常数阶O(1),对数阶O(log2n),线性阶O(n), 线性对数阶O(nlog2n),平方阶O(n2),立方阶O(n3),..., k次方阶O(nk),指数阶O(2n)。随着问题规模n的不断增大,上述时间复杂度不断增大,算法的执行效率越低。(引用网络)

  • 大O符号

    O(g(n))={ f(n): 存在正常数c和n0,使所有n>n0,有0≦f(n)≦c*g(n)}
    上面的定义说明了O(g(n))是一个函数集合,集合里面的函数满足g(n)的常数倍是函数f(n)的一个上界,即f(n)有上界。

  • Ω记号

    Ω(g(n))={ f(n):存在正常数c和n0,使所有n>n0,有0≦ c*g(n)≦f(n)}
    上面的定义说明集合里面的函数满足g(n)的常数倍是函数f(n)的一个下界,即f(n)有下界。

  • Θ记号

    Θ(g(n)),当且仅的,f(n)属于O(g(n))和Ω(g(n))。
    可见Θ是更强的形式。Θ蕴含大O和Ω。

第十二章-算法分析

1.1基础总结

  • 算法分析是计算机科学的基础课题。
  • 增长函数显示了与问题大小相关的时间或空间利用率。
  • 算法的阶有算法增长函数的主项决定。
  • 算法的阶给出乐算法增长函数的上界。
  • 更快的处理器不能弥补当问题的大小增长时算法的的效率。
  • 分析算大的复杂度时经常需要分析循环的执行情况。
  • 嵌套循环的分析必须要考虑内层和外层循环的执行情况。

1.2到底啥子是算法

  1. 简单来说,算法就是一系列被控制的步骤,你通过按序执行这些步骤可以实现一些目标或者产生一些输出。
  2. 就好比在Windows上打开一个软件的方法步骤(这应该可以算作一个算发吧...)
puclic void 开软件1(){
    "
    1.找到桌面快捷方式
    2.双击鼠标左键
    "
}
public void 开软件2(){
    "
    1.打开我的电脑
    2.在电脑硬盘中找到安装目录
    3.在安装路径中找的软件的主程序模块
    4.单击鼠标右键
    5.在弹出的菜单中选择"打开"
    
    "
  
}

3.就犹如你可以有很多种打开一个软件的方式一样,你可以用多种不同的算法来解决同一个问题。打开方式的麻烦程度就好比解决这问题的效率。有的解决办法效率更高,比其他方法需要更少的时间和空间。问题是如何分析那个算法效率高。

2.1算法分析

  • 算法是解决问题的方法,一个问题可以有多种解决方法,不同的算法之间就有了优劣之分。如何对算法进行比较呢?算法可以比较的方面很多,如易读性、健壮性、可扩展性等,但不是最关键的方面,算法的核心和灵魂是效率,也就是解决问题的速度。试想,一个需要运行很多年才能给出正确结果的算法,就是其他方面的性能再好,也是一个不实用的算法。

判断算法性能的一个基本考虑是处理一定“规模”的输入时该算法所需要执行的“基本操作”数。“规模”一般指输入量的数目。一个“基本操作”必须具备这样的性质:完成该操作所需时间和操作数的具体取值无关。

## 2.2时间复杂度

  • 算法的时间复杂度被设计来评价其语句执行次数。但它又不是语句执行次数,而是次数的同数量级函数。

  • 一个算法执行所耗费的时间,从理论上是不能算出来的,一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多。

  • 一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),使得当n趋近于无穷大时,T(n)/f(n)的极限值为不等于零的常数,则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度,简称时间复杂度。时间频度不同,但时间复杂度可能相同。如:T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同,但时间复杂度相同,都为O(n2)。按数量级递增排列,常见的时间复杂度有:常数阶O(1),对数阶O(log2n),线性阶O(n), 线性对数阶O(nlog2n),平方阶O(n2),立方阶O(n3),..., k次方阶O(nk),指数阶O(2n)。随着问题规模n的不断增大,上述时间复杂度不断增大,算法的执行效率越低。

  • 大O符号

    O(g(n))={ f(n): 存在正常数c和n0,使所有n>n0,有0≦f(n)≦c*g(n)}
    上面的定义说明了O(g(n))是一个函数集合,集合里面的函数满足g(n)的常数倍是函数f(n)的一个上界,即f(n)有上界。

  • Ω记号

    Ω(g(n))={ f(n):存在正常数c和n0,使所有n>n0,有0≦ c*g(n)≦f(n)}
    上面的定义说明集合里面的函数满足g(n)的常数倍是函数f(n)的一个下界,即f(n)有下界。

  • Θ记号

    Θ(g(n)),当且仅的,f(n)属于O(g(n))和Ω(g(n))。
    可见Θ是更强的形式。Θ蕴含大O和Ω。

王彪20162321 2017-2018程序设计与数据结构-第二学期-第一周学习总结

3.1课本习题

for(int count=0;count<n;count++){
    for(int count2=0;count2 <n ; count2=count2+2){
        System.out.println(count,count2);
    }
}
public class lxr {
    public static void main(String[] args) {
        int n = 8;
        int count=0;
        int count2=0;
        for (count=0; count < n; count++)  {
            for ( count2=0; count2 < n; count2=count2+2)
            {
                System.out.println(count+","+count2);
            }
        }
        System.out.println(count==n);
        int num=n%2;
        if (num==1){
        System.out.println(count2==n+1);
        System.out.println("ji");
    }
        else {
            System.out.println(count2==n);
            System.out.println("ou");
        }
       //  count  = f(n)= n;

        //  count2 = g(n) =  { n 为奇数,g(n) = n+1; n为偶数,g(n) = n}

        //  so O(n)


    }
}

3.1书本习题

    for(int count=0;count<n;count++){
    for(int count2=0;count2 <n ; count2=count2+2){
        System.out.println(count,count2);
    }
    }
public class lxr {
    public static void main(String[] args) {
        int n = 8;
        int count=0;
        int count2=0;
        for (count=0; count < n; count++)  {
            for ( count2=0; count2 < n; count2=count2+2)
            {
                System.out.println(count+","+count2);
            }
        }
        System.out.println(count==n);
        int num=n%2;
        if (num==1){
        System.out.println(count2==n+1);
        System.out.println("ji");
    }
        else {
            System.out.println(count2==n);
            System.out.println("ou");
        }
       //  count  = f(n)= n;

        //  count2 = g(n) =  { n 为奇数,g(n) = n+1; n为偶数,g(n) = n}

        //  so O(n)


    }
}

3.2结对对象

  • 我的结对对象 20162320刘先润

  • 新学期都加油吧,大二了,你的才华撑不下你的野心的时候静下来读书吧!

  • 这章的学习看似很简单但实际是基础。从网上找到很多关于算法的帖子,博客里也有不少引用,但真正对算法的分析与比较还需要大量的练习。这里有一部分习题,接下来一段时间将会不断练习。但好像有点看不懂啊.......

  • 代码托管

4.1网络学习材料链接