计算机常用公式大全集，计算机领域必备公式大全，从基础算法到高级技巧

本文目录导读：

图片来源于网络，如有侵权联系删除

1. 基础算法
2. 数据结构
3. 高级技巧

基础算法

1、排序算法

（1）冒泡排序

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]
    return arr

（2）选择排序

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_index = i
        for j in range(i+1, n):
            if arr[min_index] > arr[j]:
                min_index = j
        arr[i], arr[min_index] = arr[min_index], arr[i]
    return arr

（3）插入排序

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i-1
        while j >=0 and key < arr[j]:
            arr[j+1] = arr[j]
            j -= 1
        arr[j+1] = key
    return arr

2、查找算法

（1）二分查找

图片来源于网络，如有侵权联系删除

def binary_search(arr, x):
    low = 0
    high = len(arr) - 1
    mid = 0
    while low <= high:
        mid = (high + low) // 2
        if arr[mid] < x:
            low = mid + 1
        elif arr[mid] > x:
            high = mid - 1
        else:
            return mid
    return -1

（2）线性查找

def linear_search(arr, x):
    for i in range(len(arr)):
        if arr[i] == x:
            return i
    return -1

数据结构

1、链表

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
def create_list(arr):
    head = ListNode(arr[0])
    cur = head
    for i in range(1, len(arr)):
        cur.next = ListNode(arr[i])
        cur = cur.next
    return head
def print_list(head):
    cur = head
    while cur:
        print(cur.val, end=' ')
        cur = cur.next
    print()

2、栈

class Stack:
    def __init__(self):
        self.items = []
    def push(self, item):
        self.items.append(item)
    def pop(self):
        return self.items.pop()
    def is_empty(self):
        return len(self.items) == 0
    def peek(self):
        return self.items[-1]

3、队列

class Queue:
    def __init__(self):
        self.items = []
    def enqueue(self, item):
        self.items.append(item)
    def dequeue(self):
        return self.items.pop(0)
    def is_empty(self):
        return len(self.items) == 0
    def size(self):
        return len(self.items)

高级技巧

1、动态规划

动态规划是一种将复杂问题分解为更小子问题，通过子问题的最优解来构建原问题的最优解的方法，以下是一个经典的动态规划问题：最长公共子序列。

图片来源于网络，如有侵权联系删除

def lcs(X, Y):
    m = len(X)
    n = len(Y)
    L = [[0] * (n+1) for i in range(m+1)]
    for i in range(m+1):
        for j in range(n+1):
            if i == 0 or j == 0:
                L[i][j] = 0
            elif X[i-1] == Y[j-1]:
                L[i][j] = L[i-1][j-1] + 1
            else:
                L[i][j] = max(L[i-1][j], L[i][j-1])
    return L[m][n]

2、深度优先搜索（DFS）

深度优先搜索是一种用于遍历或搜索树或图的算法，以下是一个使用递归实现的DFS算法：

def dfs(graph, start):
    visited = set()
    stack = [start]
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            for next_vertex in graph[vertex]:
                stack.append(next_vertex)
    return visited

3、广度优先搜索（BFS）

广度优先搜索是一种用于遍历或搜索树或图的算法，以下是一个使用队列实现的BFS算法：

from collections import deque
def bfs(graph, start):
    visited = set()
    queue = deque([start])
    while queue:
        vertex = queue.popleft()
        if vertex not in visited:
            visited.add(vertex)
            for next_vertex in graph[vertex]:
                queue.append(next_vertex)
    return visited

本文介绍了计算机领域常用的基础算法、数据结构和高级技巧，通过对这些知识的掌握，可以帮助我们更好地理解和解决实际问题，希望本文能对您的学习有所帮助。

标签： #常用计算机公式大全