时间空间复杂度

• 表示法
  O(n^n), O(n!), O(n), O(1), O(nlogn)
  这些是规模的量级，和n(数据量的大小)成比例的
• 目的
  • 评估算法的效率，即耗费的时间(计算量)和空间(存储占用)
  • 主要关注点是相对于输入数据量的规模。
  • 简单来说， 时间复杂度就是基本语句的运算次数。

要理解不同时间复杂度相对于数据量的增长速度是不一样的。

• 常用复杂度对比

  
  时间复杂度.png

1. 数有多少个循环嵌套，大概可以知道是平方立方还是更高的次方
2. 如果有“二分”这样的结构，一般会包括logn
3. 可以数一下搜索空间确定复杂度

哈希表

基本性质

• 一个存储结构，其中存储的是Key-Value对，其中Key和Value可以是任意的类型。

类似于数组，可以使用数组的下标索引去访问存储的数据，哈希表也一样，可以通过Key去访问对应的Value。不同于数组的是，数组下标只能为数字，而哈希表Key可以是任意类型。

• 类似于f(x) = y这样的函数，开发者可以设置任意f(x1) = y1，f(x2) = y2
• 也支持这样的访问形式: a = f(x1)

即，哈希表支持增删改查4种操作。
对于哈希表的增删改查，其时间复杂度都近似为O(1), 并且不依赖于插入的顺序，即随机访问(想访问哪个数据就马上访问哪个数据)
哈希表中的数据没有顺序，所以也不可以对哈希表进行排序！

哈希表和数组的不同点对比

• 数组下标为数字，而哈希表可以支持更多的数据类型
• 数组在中间插入数据的时候，时间复杂度一般不是O(1)

基本使用

代码举例：

import java.util.HashMap;

public class Main {

    public static void main(String[] args) {
//        HashMap即为哈希表实现的一个数据结构类
        HashMap<String, String> hashmap = new HashMap<String, String >(); // 声明一个哈希表数据结构

//        增加操作
        hashmap.put("Name", "Yang"); // 增
        hashmap.put("Gender", "Male"); // 增
//        查询操作
        if(hashmap.containsKey("Name")) {
            System.out.println(hashmap.get("Name")); // Yang
        }
//        对于查询操作，如果Key不存在，get方法会返回null，也可以通过这个来判断
//        String value = hashmap.get("Name");
//        if(value != null) {
//            System.out.println(value);
//        }
//        修改操作 和 新增操作一样  会覆盖同样的Key值
        hashmap.put("Gender", "Female"); // 覆盖掉
        System.out.println(hashmap.get("Gender")); // Female
//        删除 remove
        hashmap.remove("Gender");
        System.out.println(hashmap.get("Gender")); // null
    }


}

基本实现原理

基本实现思路为把任意的Key值转换为数字，然后作为数组的下标，然后把Value存储在数组下标对应位置上。

ValueClass[] array = new ValueClass[size];

比如：

1. 修改操作：

String key = someString();
int index = hash(key); // 找到哈希表对应的Key对应的数字下标
array[index] = value;

2.访问操作

int index = hash(key);
ValueClass value = array[index];

栈

一个数据结构，用于存储数据，支持2种操作：

• 插入数据(push)
• 取出数据(pop)，获得数据同时将数据从栈中删除

所有操作的时间复杂度均为O(1)

跟哈希表不同的是，哈希表可以随机访问，但是栈对数据访问顺序做了限制，先进后出，后进先出，即访问的话只能访问到最近放进栈里的那个数据

函数调用栈

假设现有如下函数

function f1() {
    f2();
    someCode...
}

function f2() {
    f3();
    someCode...
}

调用f1时，会将此时f1的状态压入栈中，然后调用f2,再将f2此时的状态压入栈中，再去调用f3(),f3()调用完成后再从栈中取出f2的状态继续执行，执行完后再次从栈中取出f1的状态继续执行。

基本使用

import java.util.Stack;

public class Main {

    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<Integer>();
        stack.push(3); // 增
        stack.push(5); // 增
        
        System.out.println(stack.pop()); // 5
        System.out.println(stack.pop()); // 3
    }

}

栈的额外操作

• 使用peek()可以查看栈顶端的数据同时又不删除该数据
• 使用empty()可以查看栈是否为空

队列

一个类似于栈的数据结构，用于存储数据，同样支持2种操作

• 插入数据(add)
• 取出数据(poll)，获得数据，同时从队列中删除该数据

所有操作的时间复杂度均为O(1)

队列遵循一个先进先出，后进后出的顺序，即在队列中取出数据的顺序和放进去的顺序是一样的。

队列使用举例

public class Main {

    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<Integer>();

        queue.add(3);
        queue.add(5);

        System.out.println(queue.peek()); // 3

        System.out.println(queue.poll()); // 3
        System.out.println(queue.poll()); // 5

        System.out.println(queue.isEmpty()); // true
    }

}