算法之旅(二) 初识数据结构与算法复杂度

一、常用数据结构概览

数组（Array）
链表（Linked List）
栈（Stack）
队列（Queue）
哈希表（Hash Table）
树（Tree）
图（Graph）
堆（Heap）
集合（Set）
字典树（Trie）

二、数据结构的详细介绍

1. 数组（Array）

特点：
- 连续内存分配：数组中的元素在内存中连续存储。
- 固定大小：数组的大小在初始化后不能改变。
- 快速访问：可以通过索引快速访问元素，时间复杂度为 O(1)。
适用场景：
- 需要快速随机访问元素的场景。

示例代码：

int[] numbers = new int[5];
numbers[0] = 10;
int firstNumber = numbers[0]; // O(1) 访问

2. 链表（Linked List）

特点：
- 动态大小：可以随时增加或删除元素。
- 节点结构：由节点组成，每个节点包含数据和指向下一个节点的引用。
- 顺序访问：访问元素需要从头节点开始，时间复杂度为 O(n)。
分类：
- 单向链表：每个节点指向下一个节点。
- 双向链表：每个节点有指向前一个和后一个节点的引用。
适用场景：
- 需要频繁插入和删除元素的场景。

示例代码：

class Node {
    int data;
    Node next;
    Node(int data) {
        this.data = data;
    }
}

// 创建链表
Node head = new Node(10);
head.next = new Node(20);

3. 栈（Stack）

特点：
- 后进先出（LIFO）：最后入栈的元素最先出栈。
常用操作：
- push：入栈，时间复杂度 O(1)。
- pop：出栈，时间复杂度 O(1)。
适用场景：
- 处理递归、表达式求值、浏览器历史记录等。

示例代码：

Stack<Integer> stack = new Stack<>();
stack.push(10);
int top = stack.pop(); // O(1)

4. 队列（Queue）

特点：
- 先进先出（FIFO）：最先入队的元素最先出队。
常用操作：
- enqueue：入队，时间复杂度 O(1)。
- dequeue：出队，时间复杂度 O(1)。
适用场景：
- 任务调度、广度优先搜索等。

示例代码：

Queue<Integer> queue = new LinkedList<>();
queue.add(10);
int first = queue.poll(); // O(1)

5. 哈希表（Hash Table）

特点：
- 键值对存储：通过键（Key）访问对应的值（Value）。
- 快速查找：平均情况下，插入、删除、查找的时间复杂度为 O(1)。
适用场景：
- 需要快速插入、删除、查找的场景。

示例代码：

Map<String, Integer> map = new HashMap<>();
map.put("apple", 3);
int count = map.get("apple"); // O(1)

6. 树（Tree）

特点：
- 层次结构：由节点和边组成的分层数据结构。
分类：
- 二叉树：每个节点最多有两个子节点。
- 二叉搜索树（BST）：左子节点小于父节点，右子节点大于父节点。
- 平衡树：如红黑树、AVL树，保持树的平衡性。
适用场景：
- 实现高效的查找、排序、范围查询等。

示例代码：

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

// 创建二叉树节点
TreeNode root = new TreeNode(10);
root.left = new TreeNode(5);
root.right = new TreeNode(15);

7. 图（Graph）

特点：
- 节点（顶点）和边：表示物体和它们之间的关系。
表示方法：
- 邻接矩阵：二维数组表示节点之间的连接。
- 邻接表：每个节点的邻居列表。
适用场景：
- 社交网络、地图导航、任务调度等。

示例代码：

// 使用邻接表表示图
Map<String, List<String>> graph = new HashMap<>();
graph.put("A", Arrays.asList("B", "C"));
graph.put("B", Arrays.asList("A", "D"));

8. 堆（Heap）

特点：
- 完全二叉树：所有节点都满足堆的性质。
- 大顶堆：每个父节点的值都大于等于其子节点。
- 小顶堆：每个父节点的值都小于等于其子节点。
适用场景：
- 实现优先队列、排序（堆排序）、求解 Top K 问题等。

示例代码：

// 小顶堆
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.add(5);
minHeap.add(2);
int smallest = minHeap.poll(); // 2

9. 集合（Set）

特点：
- 元素唯一性：不包含重复元素。
适用场景：
- 去重操作、集合运算（交集、并集、差集）等。

示例代码：

Set<String> set = new HashSet<>();
set.add("apple");
set.add("banana");
boolean exists = set.contains("apple"); // true

10. 字典树（Trie）

特点：
- 前缀树：用于高效地存储和检索字符串集合，尤其是字符串前缀共享的集合。
适用场景：
- 自动补全、拼写检查、前缀查询等。

示例代码：

class TrieNode {
    boolean isWord;
    Map<Character, TrieNode> children = new HashMap<>();
    TrieNode() {
        isWord = false;
    }
}

// 插入单词
void insert(TrieNode root, String word) {
    TrieNode node = root;
    for (char c : word.toCharArray()) {
        node.children.putIfAbsent(c, new TrieNode());
        node = node.children.get(c);
    }
    node.isWord = true;
}

三、算法复杂度

算法复杂度用于评估算法的性能，主要分为时间复杂度和空间复杂度。

1. 时间复杂度（Time Complexity）

定义：算法执行所需时间与输入规模之间的函数关系。

常见时间复杂度类型及示例

O(1) - 常数时间复杂度
- 描述：算法的执行时间不随输入规模变化。
- 示例：访问数组中的某个元素。
```
int getFirstElement(int[] arr) {
    return arr[0]; // O(1)
}
```

O(log n) - 对数时间复杂度

描述：算法的执行时间随输入规模的对数增长。

示例：二分查找。

int binarySearch(int[] arr, int target) {
    int left = 0, right = arr.length -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            return mid; // O(log n)
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid -1;
        }
    }
    return -1;
}

O(n) - 线性时间复杂度

描述：算法的执行时间与输入规模成正比。

示例：遍历数组。

int sumArray(int[] arr) {
    int sum = 0;
    for (int num : arr) {
        sum += num; // O(n)
    }
    return sum;
}

O(n log n) - 线性对数时间复杂度

描述：常见于高效排序算法，如归并排序、快速排序。

示例：归并排序。

void mergeSort(int[] arr, int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        mergeSort(arr, left, mid);       // O(log n)
        mergeSort(arr, mid + 1, right);  // O(log n)
        merge(arr, left, mid, right);    // O(n)
    }
}

O(n²) - 二次时间复杂度

描述：算法的执行时间与输入规模的平方成正比。

示例：冒泡排序。

void bubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {           // O(n)
        for (int j = 0; j < n - i - 1; j++) {   // O(n)
            if (arr[j] > arr[j +1]) {
                // 交换
                int temp = arr[j];
                arr[j] = arr[j +1];
                arr[j +1] = temp;
            }
        }
    }
}

时间复杂度优先级排行（从高效到低效）

O(1) - 常数时间
O(log n) - 对数时间
O(n) - 线性时间
O(n log n) - 线性对数时间
O(n²) - 二次时间
O(2ⁿ) - 指数时间
O(n!) - 阶乘时间

2. 空间复杂度（Space Complexity）

定义：算法执行过程中所需的额外空间与输入规模之间的函数关系。

常见空间复杂度类型及示例

O(1) - 常数空间复杂度
- 描述：算法所需的额外空间不随输入规模变化。
- 示例：在原地交换两个变量。
```
void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
    // O(1) 空间
}
```

O(n) - 线性空间复杂度

描述：算法所需的额外空间与输入规模成正比。

示例：创建一个新数组存储输入数组的副本。

int[] copyArray(int[] arr) {
    int n = arr.length;
    int[] newArr = new int[n]; // O(n) 空间
    for (int i = 0; i < n; i++) {
        newArr[i] = arr[i];
    }
    return newArr;
}

O(n²) - 二次空间复杂度
- 描述：算法所需的额外空间与输入规模的平方成正比。
- 示例：创建一个二维矩阵。
```
int[][] matrix = new int[n][n]; // O(n²) 空间
```

空间复杂度优先级排行（从高效到低效）

O(1) - 常数空间
O(log n) - 对数空间（通常出现在递归调用的栈空间中）
O(n) - 线性空间
O(n log n)
O(n²) - 二次空间

四、复杂度优先级总结

时间复杂度优先级（从高效到低效）：
1. O(1)
2. O(log n)
3. O(n)
4. O(n log n)
5. O(n²)
6. O(2ⁿ)
7. O(n!)
空间复杂度优先级（从高效到低效）：
1. O(1)
2. O(log n)
3. O(n)
4. O(n log n)
5. O(n²)

数据结构：选择合适的数据结构对于算法的效率至关重要。先了解所有常用的数据结构，然后深入理解其特点、操作和适用场景。
算法复杂度：时间复杂度和空间复杂度是衡量算法性能的两个重要指标。了解各种复杂度类型及其优先级，有助于在开发中选择最优的算法和数据结构。

算法之旅(二) 初识数据结构与算法复杂度

算法之旅(二) 初识数据结构与算法复杂度

1. 数组（Array）

2. 链表（Linked List）

3. 栈（Stack）

4. 队列（Queue）

5. 哈希表（Hash Table）

6. 树（Tree）

7. 图（Graph）

8. 堆（Heap）

9. 集合（Set）

10. 字典树（Trie）

1. 时间复杂度（Time Complexity）

常见时间复杂度类型及示例

时间复杂度优先级排行（从高效到低效）

2. 空间复杂度（Space Complexity）

常见空间复杂度类型及示例

空间复杂度优先级排行（从高效到低效）

相关阅读更多精彩内容

友情链接更多精彩内容