Java常用数据结构与算法概述

更新时间:2020-05-27 11:11:42 点击次数:882次
数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下,精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。(引用百度百科对数据结构的定义)常用的数据结构有以下几种

算法(Algorithm)是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制。也就是说,能够对一定规范的输入,在有限时间内获得所要求的输出。如果一个算法有缺陷,或不适合于某个问题,执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用***空间复杂度***与***时间复杂度***来衡量(引用百度百科对数据结构的定义)
时间复杂度:在计算机科学中,时间复杂性,又称时间复杂度,算法的时间复杂度是一个函数,它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述,不包括这个函数的低阶项和首项系数。使用这种方式时,时间复杂度可被称为是渐近的,亦即考察输入值大小趋近无穷时的情况。
一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。
一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),使得当n趋近于无穷大时,T(n)/f (n)的极限值为不等于零的常数,则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度,简称时间复杂度。
在各种不同算法中,若算法中语句执行次数为一个常数,则时间复杂度为O(1),另外,在时间频度不相同时,时间复杂度有可能相同,如T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同,但时间复杂度相同,都为O(n2)。
空间复杂度 空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度,记做S(n)=O(f(n))。
常见的时间复杂度并且它们的时间复杂度从小到大依次为

常数阶O(1)
对数阶O(log2^n)
线性阶O(n)
线性对数阶O(nlog2^n)
平方阶O(n^2)
立方阶O(n^3)
n次方阶O(n^n)
指数阶O(2^n)
下面举例说明几种时间复杂度的理解及代码演示

1.常数阶

  /**常数阶 无论代码执行多少行 ,它没有循环等复杂结构,就执行了一次,那么这代码的时间复杂度就是o(1)
    下面的代码执行的时候,消耗的时间不随某个变量的变化而变化。所以说无论它的代码行数有多长,都可以用O(1)表示*/
    public static void main(String[] args) {
        int i=1;
        int j=2;
        i++;
        j++;
        int m=i+j;
    }

2.对数阶O(log2^n)

   /**对数阶
     * 下面这段代码每执行一次i就接近 n (注意:这个n不可变,在这里我只是给他赋一个初始值) 所以说执行2的x次方后的值不小于n的时候
     * 程序停止
     *  也就是2^n=x;
     *  x=log2^n; 所以这个代码的时间复杂度就为O(log2^n)
     *  这个2为下面代码i*2的2,如果i*3那么则为O(log3^n)
     */
    public static void main(String[] args) {
       int i=1;
       int n=100;
       while (i<n){
           i=i*2;
       }
    }

3.线性阶O(n)

  /**线性阶O(n)
     *  (注意:这个n不可变,在这里我只是给他赋一个初始值)
     *  下面这段代码会执行n次,它消耗的时间随着n的变化而变化
     *  因此这类代码的时间复杂度可以用O(n)来表示
     */
    public static void main(String[] args) {
        int n=100;
       for(int i=0;i<=n;i++){
           System.out.println("我爱java");
       }
    }

4.线性对数阶O(nlog2^n)

   /**线性阶对数阶O(n*log^2)
     *  (注意:这个n不可变,在这里我只是给他赋一个初始值)
     * 只要理解了前面的几种情况,这种情况应该很好理解 就是在lon2^n的基础上乘以n
     * 对应代码就是最外层弄一个n次循环
     */
    public static void main(String[] args) {
        int i=1;
        int n=100;
       for(int m=1;m<=n;m++){
           while (i<n){
               i=i*2;
               System.out.println("我爱java");
           }
       }
    }

5.平方阶O(n^2)

 /**平方阶O(n^2)
     *  (注意:这个n不可变,在这里我只是给他赋一个初始值)
     *  这个就更好理解了 就是把O(n)的代码再嵌套循环一遍就是o(n^2)
     *  同样道理 o(n^3)及多次方就是多几重循环罢了;
     *  就不一一列举
     */
    public static void main(String[] args) {
        int n=100;
       for(int m=1;m<=n;m++){
           for(int i=1;i<=n;i++){
               System.out.println("我爱java");
           }
       }
    }

队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。(引用百度百科)

栈(stack)又名堆栈,它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素

**堆(Heap)**是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵完全二叉树的数组对象。

树状图是一种数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。它具有以下的特点:
每个结点有零个或多个子结点;没有父结点的结点称为根结点;每一个非根结点有且只有一个父结点;除了根结点外,每个子结点可以分为多个不相交的子树。

本站文章版权归原作者及原出处所有 。内容为作者个人观点, 并不代表本站赞同其观点和对其真实性负责,本站只提供参考并不构成任何投资及应用建议。本站是一个个人学习交流的平台,网站上部分文章为转载,并不用于任何商业目的,我们已经尽可能的对作者和来源进行了通告,但是能力有限或疏忽,造成漏登,请及时联系我们,我们将根据著作权人的要求,立即更正或者删除有关内容。本站拥有对此声明的最终解释权。

回到顶部
嘿,我来帮您!