数据结构

[huangchucai]

数据结构

一、时间复杂度

• 概念： 一个算法问题不断增大时对应的时间增长曲线
  

• 常见的时间复杂度
  表
  

• 实例分析

  1. O(1) : 取得样本数据的时间不会因为样本的多少而改变

     例子： 比如取快递的用的快递箱，每次收到丰巢给你发的取货码的时候，你取快递的时间不会因为快递箱的多少而发生改变，一直都是输入取货码的之后，就弹出快递了。再比如我的身后有一排柜子，里面有香蕉（代号B），苹果（代号A），葡萄（G），现在你说A，我迅速的就把苹果递过来了；你说B，我迅速就把香蕉递过来了。就算你再增加菠萝（P）、火龙果(H)，但是你说一个代号，我递给你相应的水果这个速度是几乎不会变的。

  2. O(n)：随着样本数量的增长，复杂度也会成线性的增长。

     例子： 就像我们数数字，从1数到100，需要100秒，那么从1从200，基本上不会小于200，所以数数字是一个O(n)。再比如，我们要设计一个算法从一堆杂乱的试卷中找出最高分数，这就需要我们从头到尾看完每一份试卷，显然试卷越多，所需要的时间也越多

  3. O(n²)：计算的复杂度随着样本个数以平方数增长。比如冒泡，选择排序。

     例子：就像例子2中的找最高分的试卷，等我们找出最高的分数之后，然后一边另起一堆，然后用同样的方式再找第二高的分数，再放到新堆上。。。。。。这样我们做n次，试卷就按照从低到高都排好了。因为有n分试卷，所以这种翻试卷，找最高分的行为，我们要做n次，每次的复杂度都是0(n), n次就是O(n²)

  4. O(nlogn): 计算的复杂度随着样本个数以对数增长。比如：二分查找

     例子：例子3中的试卷已经按照从低到高的排序了，我们现在要 查找59分一下的试卷。先翻到中间，把试卷堆由中间分成上下两堆，看中间这份是大于还是小于59，如果大于，就留下上面那堆，别的丢掉，如果小于，就留下下面那堆，丢掉上面。然后按照同样的方法，每次丢一半的试卷，直到丢无可丢为止。

参考链接

二、哈希表

1. 算法复杂度：O(1)

​ 哈希表通过哈希函数来映射的，当我们拿到一个关键字的时候，用哈希函数转换一下，直接从表中取得对应的值。和数据的多少没有关系，故而每次执行的时间都是一样的（但实际上会有一些冲突等需要处理）

2. 特性

• 元素之间不需要逻辑关系， 随机访问，想访问哪一个数据就可以马上得到结果
• 键值对的形式key Value，可以是任意类型，但是key不能够重复
• 增删改查的时间复杂度都近似于O(1)
• 哈希表里面的数据没有顺序，不能够进行哈希表排序

3.实例

public class hashMap {
    public static void main(String[] args) {
        HashMap<String, String> gender = new HashMap<String, String>();  // 哈希表实现的一个Map, 声明一个哈希表
        // 增加
        gender.put("hcc", "male");
        gender.put("yx", "woman");
        // 删除
        gender.remove("yx");

        // 查找
        if (gender.containsKey("hcc")) {
            System.out.println(gender.get("hcc"));
        }
        // 修改 （直接覆盖)
        gender.put("yx", "female");
        System.out.println(gender.get("yx"));
    }
}

三、栈

1. 算法复杂度： O(1)

​ 由于栈的先入后出，后入先出（Last in first out）的关系，就是只能访问当最近放进到栈里面的那个数据~，所以所有的操作都是O(1)

2. 特性

• 先入后出，后入先出
• 数据插入读取块，但是对读取的顺序有要求，不像哈希可以随机访问
• 取不是顶层的值会很慢

3. 实例

public class StackStudy {
    public static void main(String[] args) {
        Stack<String> stack = new Stack<String>();

        // 增加
        stack.push("yx");
        // 取出并删除顶层元素
        String name = stack.pop();
        // 判断是否为空
        System.out.println(stack.empty());
        // 单独的取出元素不删除
        stack.push("hcc");
        String hcc = stack.peek();
        System.out.println(hcc);
        System.out.println(stack.empty());
    }

}

四、队列

1. 算法时间复杂度： O(1)

2.特性

• 先进先出，后进后出
• 取不是顶层的数据比较慢

3. 实例

public class QueueStudy {
    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.add(2);
        queue.add(3);
        // 取出first 但是不删除
        int age = queue.peek();
        System.out.println(age);
        // 取出first 并删除
        int age2 = queue.poll();
        int age3 = queue.poll();
        System.out.println(age2); 
        System.out.println(age3); // 3
    }
}