algorithm-study

数据结构与算法学习笔记

算法和数据结构是程序员的基本功，本文总结了常用的数据结构和算法。

基础数据结构

1. 数组 (Array)

特点：

连续内存存储
随机访问，时间复杂度O(1)
插入删除操作复杂度O(n)

应用场景：

需要频繁随机访问元素
数据量相对固定

2. 链表 (Linked List)

特点：

非连续内存存储
插入删除操作复杂度O(1)
访问元素复杂度O(n)

代码示例：

1
class ListNode:
2
    def __init__(self, val=0, next=None):
3
        self.val = val
4
        self.next = next
5

6
class LinkedList:
7
    def __init__(self):
8
        self.head = None
9

10
    def insert(self, val):
11
        new_node = ListNode(val)
12
        new_node.next = self.head
13
        self.head = new_node
14

15
    def delete(self, val):
16
        if not self.head:
17
            return
18

19
        if self.head.val == val:
20
            self.head = self.head.next
21
            return
22

23
        current = self.head
24
        while current.next and current.next.val != val:
25
            current = current.next
26

27
        if current.next:
28
            current.next = current.next.next

3. 栈 (Stack)

特点：

后进先出 (LIFO)
主要操作：push、pop、peek

应用场景：

函数调用栈
表达式求值
括号匹配

4. 队列 (Queue)

特点：

先进先出 (FIFO)
主要操作：enqueue、dequeue

应用场景：

广度优先搜索
任务调度
缓冲区

常用算法

1. 排序算法

快速排序

1
def quick_sort(arr, low, high):
2
    if low < high:
3
        pi = partition(arr, low, high)
4
        quick_sort(arr, low, pi - 1)
5
        quick_sort(arr, pi + 1, high)
6

7
def partition(arr, low, high):
8
    pivot = arr[high]
9
    i = low - 1
10

11
    for j in range(low, high):
12
        if arr[j] <= pivot:
13
            i += 1
14
            arr[i], arr[j] = arr[j], arr[i]
15

16
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
17
    return i + 1

时间复杂度：

平均情况：O(n log n)
最坏情况：O(n²)

归并排序

1
def merge_sort(arr):
2
    if len(arr) <= 1:
3
        return arr
4

5
    mid = len(arr) // 2
6
    left = merge_sort(arr[:mid])
7
    right = merge_sort(arr[mid:])
8

9
    return merge(left, right)
10

11
def merge(left, right):
12
    result = []
13
    i = j = 0
14

15
    while i < len(left) and j < len(right):
16
        if left[i] <= right[j]:
17
            result.append(left[i])
18
            i += 1
19
        else:
20
            result.append(right[j])
21
            j += 1
22

23
    result.extend(left[i:])
24
    result.extend(right[j:])
25
    return result

时间复杂度： O(n log n)

2. 搜索算法

二分搜索

1
def binary_search(arr, target):
2
    left, right = 0, len(arr) - 1
3

4
    while left <= right:
5
        mid = (left + right) // 2
6
        if arr[mid] == target:
7
            return mid
8
        elif arr[mid] < target:
9
            left = mid + 1
10
        else:
11
            right = mid - 1
12

13
    return -1

时间复杂度： O(log n)

算法复杂度分析

时间复杂度

O(1) - 常数时间
O(log n) - 对数时间
O(n) - 线性时间
O(n log n) - 线性对数时间
O(n²) - 平方时间

空间复杂度

分析算法所需的额外存储空间。

学习建议

理论与实践结合 - 理解原理后动手实现
多做练习 - LeetCode、牛客网等平台
总结归纳 - 整理常见题型和解题模板
复杂度分析 - 养成分析时间空间复杂度的习惯

总结

数据结构和算法是编程的基础，需要持续练习和总结。掌握常用的数据结构和算法对于解决实际问题和面试都非常重要。