跳转到内容

算法与数据结构

来自代码酷

算法与数据结构[编辑 | 编辑源代码]

算法与数据结构是计算机科学的核心基础，研究如何高效地组织和处理数据。算法指解决问题的一系列明确步骤，数据结构则是存储和组织数据的方式。两者相辅相成，共同构成了高效程序设计的理论基础和实践工具。

基本概念[编辑 | 编辑源代码]

算法[编辑 | 编辑源代码]

算法是具有以下特性的计算过程：

  • 有限性：必须在有限步骤后终止
  • 确定性：每个步骤都有明确定义
  • 输入：有零个或多个输入
  • 输出：产生至少一个输出
  • 有效性：每个步骤都能在有限时间内完成

数据结构[编辑 | 编辑源代码]

常见的基本数据结构包括：

  • 数组：连续内存空间存储相同类型元素
  • 链表：通过指针连接的节点序列
  • 栈：后进先出(LIFO)的线性结构
  • 队列：先进先出(FIFO)的线性结构
  • 树：具有层次关系的非线性结构
  • 图：由顶点和边组成的网络结构

复杂度分析[编辑 | 编辑源代码]

算法效率通常用大O符号表示：

O(1)<O(log⁡n)<O(n)<O(nlog⁡n)<O(n2)<O(2n)

时间复杂度示例： 

# O(1) 常数时间
def get_first(arr):
    return arr[0]

# O(n) 线性时间
def linear_search(arr, target):
    for item in arr:
        if item == target:
            return True
    return False

# O(n^2) 平方时间
def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

经典算法[编辑 | 编辑源代码]

排序算法[编辑 | 编辑源代码]

搜索算法[编辑 | 编辑源代码]

应用实例[编辑 | 编辑源代码]

路径规划[编辑 | 编辑源代码]

使用Dijkstra算法寻找图中两点间最短路径：

graph LR A((A)) --5--> B((B)) A --3--> C((C)) B --2--> D((D)) C --7--> D C --1--> E((E)) D --4--> F((F)) E --2--> F

数据压缩[编辑 | 编辑源代码]

哈夫曼编码利用字符出现频率构建最优前缀码： 

from heapq import heappop, heappush

def build_huffman_tree(freq):
    heap = [[weight, [char, ""]] for char, weight in freq.items()]
    heapify(heap)
    while len(heap) > 1:
        lo = heappop(heap)
        hi = heappop(heap)
        for pair in lo[1:]:
            pair[1] = '0' + pair[1]
        for pair in hi[1:]:
            pair[1] = '1' + pair[1]
        heappush(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])
    return heap[0]

学习资源[编辑 | 编辑源代码]

参见[编辑 | 编辑源代码]

检索自“https://wiki.echo.cool/index.php?title=算法与数据结构&oldid=5045”