当前位置： 首页 > news >正文

有哪些重大影响的算法？

news 来源：原创 2024/9/29 9:37:27

一、对互联网有重大影响的算法

在互联网的发展过程中，许多算法对其产生了深远的影响。以下是一些在互联网领域中具有重大影响的算法：

1. 加密算法

对称加密
  • AES（Advanced Encryption Standard）：
    • 广泛用于保护数据的加密标准。
    • 提供高效的加密和解密过程，常用于HTTPS、VPN和无线网络安全。
非对称加密

  • RSA（Rivest-Shamir-Adleman）：

    • 用于密钥交换和数字签名。
    • 提供安全的公钥加密，广泛应用于SSL/TLS协议中。

  • ECC（Elliptic Curve Cryptography）：

    • 提供与RSA相同的安全级别但密钥长度更短，效率更高。
    • 常用于现代加密通信协议，如TLS和SSH。
哈希算法
  • SHA-256（Secure Hash Algorithm 256-bit）：
    • 用于数据完整性验证和数字签名。
    • 广泛应用于加密货币、SSL证书和数据完整性检查。

2. 搜索算法

  • PageRank：

    • 由Larry Page和Sergey Brin发明，用于谷歌搜索引擎。
    • 通过计算网页的链接关系，评估网页的重要性，提高搜索结果的相关性和质量。

  • TF-IDF（Term Frequency-Inverse Document Frequency）：

    • 用于信息检索和文本挖掘。
    • 评估单词在文档和整个文档集合中的重要性，提高搜索引擎的文本相关性判断。

3. 压缩算法

  • Huffman编码：

    • 用于数据压缩，通过构建字符频率的二叉树实现高效编码。
    • 应用于各种文件压缩和传输协议，如ZIP和JPEG。

  • LZ77（Lempel-Ziv 1977） 和 LZW（Lempel-Ziv-Welch）：

    • 基于字典的压缩算法，广泛用于文本和图像压缩。
    • 应用于文件压缩格式如ZIP和GIF。

4. 网络流量和路由算法

  • Dijkstra算法：

    • 最短路径算法，用于计算图中从单一源点到其他节点的最短路径。
    • 广泛应用于路由协议如OSPF（Open Shortest Path First）。

  • BGP（Border Gateway Protocol）：

    • 互联网主干路由协议，负责不同自治系统（AS）之间的路由选择。
    • 通过路径向量算法选择最优路径，确保互联网的高效和稳定运行。

5. 推荐算法

  • 协同过滤：

    • 用于推荐系统，通过分析用户的历史行为和相似用户的偏好进行推荐。
    • 广泛应用于电子商务网站（如亚马逊）、流媒体服务（如Netflix）和社交媒体平台。

  • 内容推荐算法：

    • 基于内容特征（如文本、图像、视频等）进行推荐。
    • 应用于新闻推荐、内容分发网络（CDN）和个性化信息流（如Facebook、Twitter）。

6. 机器学习和数据挖掘算法

  • 决策树：

    • 基于数据特征构建树状模型，用于分类和回归任务。
    • 应用于信用评分、医疗诊断和客户细分等领域。

  • 神经网络和深度学习：

    • 模仿人脑结构的算法，用于图像识别、自然语言处理和语音识别。
    • 通过卷积神经网络（CNN）和循环神经网络（RNN）实现复杂任务的自动化和智能化。

7. 分布式计算和共识算法

  • MapReduce：

    • 分布式计算框架，用于大规模数据处理。
    • 被Hadoop等平台采用，实现数据的并行处理和分布式存储。

  • Paxos 和 Raft：

    • 分布式系统中的共识算法，用于在不可靠网络环境中实现一致性。
    • 应用于分布式数据库（如Google Spanner）、分布式文件系统和区块链技术。

总结

这些算法通过提高数据安全性、信息检索效率、数据压缩率、网络路由优化、个性化推荐、智能分析和分布式系统一致性等方面，对互联网的发展产生了深远的影响。它们不仅支撑了现有的互联网服务和应用，还推动了技术的创新和进步。

二 、八大排序算法应用场景

八大排序算法各有优缺点和适用的场景。下面简要介绍每个排序算法及其典型应用场景：

1. 冒泡排序 (Bubble Sort)

概述
  • 时间复杂度: 最优 (O(n))、平均 (O(n^2))、最坏 (O(n^2))
  • 空间复杂度: (O(1))
  • 稳定性: 稳定
应用场景
  • 小数据集: 冒泡排序简单易实现，适合处理小规模数据。
  • 教学用途: 常用于教学和学习排序算法的基本概念。

2. 选择排序 (Selection Sort)

概述
  • 时间复杂度: 最优 (O(n^2))、平均 (O(n^2))、最坏 (O(n^2))
  • 空间复杂度: (O(1))
  • 稳定性: 不稳定
应用场景
  • 小数据集: 适合数据量小且对稳定性要求不高的场景。
  • 内存受限: 空间复杂度低，可以在内存非常有限的环境中使用。

3. 插入排序 (Insertion Sort)

概述
  • 时间复杂度: 最优 (O(n))、平均 (O(n^2))、最坏 (O(n^2))
  • 空间复杂度: (O(1))
  • 稳定性: 稳定
应用场景
  • 小数据集: 高效处理小规模数据集。
  • 部分有序数据: 对于几乎有序的数据，插入排序效率较高。
  • 实时系统: 可以在实时系统中用于少量数据的排序。

4. 归并排序 (Merge Sort)

概述
  • 时间复杂度: 最优 (O(n \log n))、平均 (O(n \log n))、最坏 (O(n \log n))
  • 空间复杂度: (O(n))
  • 稳定性: 稳定
应用场景
  • 大数据集: 适合处理大型数据集。
  • 外部排序: 常用于需要外部存储（磁盘）的排序操作。
  • 并行处理: 可以并行化提高效率。

5. 快速排序 (Quick Sort)

概述
  • 时间复杂度: 最优 (O(n \log n))、平均 (O(n \log n))、最坏 (O(n^2))
  • 空间复杂度: (O(\log n))
  • 稳定性: 不稳定
应用场景
  • 大数据集: 常用于处理大型数据集，快速排序的平均时间复杂度低。
  • 通用排序: 适合大多数的排序需求，是实用性最强的排序算法之一。

6. 希尔排序 (Shell Sort)

概述
  • 时间复杂度: 根据增量序列不同，最优 (O(n \log n))、平均 (O(n^{1.3}))、最坏 (O(n^2))
  • 空间复杂度: (O(1))
  • 稳定性: 不稳定
应用场景
  • 中等规模数据集: 适合中等规模数据的排序。
  • 性能优化: 需要比插入排序和选择排序更快的排序方案，但不需要最优解。

7. 堆排序 (Heap Sort)

概述
  • 时间复杂度: 最优 (O(n \log n))、平均 (O(n \log n))、最坏 (O(n \log n))
  • 空间复杂度: (O(1))
  • 稳定性: 不稳定
应用场景
  • 大数据集: 适合处理大规模数据。
  • 内存受限: 空间复杂度较低，可以在内存有限的环境中使用。
  • 优先队列: 可用于实现优先队列等数据结构。

8. 计数排序 (Counting Sort)

概述
  • 时间复杂度: 最优 (O(n + k))、平均 (O(n + k))、最坏 (O(n + k))，其中k是范围大小
  • 空间复杂度: (O(n + k))
  • 稳定性: 稳定
应用场景
  • 范围有限的数据: 适合处理数据范围有限且范围比数据量小的数据集（如考试成绩）。
  • 整数排序: 常用于排序整数（特别是小整数）。

总结

每种排序算法都有其适用的特定场景，选择合适的排序算法取决于数据规模、数据特性和具体的需求。在实际应用中，常用的排序算法包括快速排序、归并排序和堆排序，而对于特定场景，可以选择更加适合的算法，如计数排序用于范围有限的数据，插入排序用于几乎有序的数据等。

三、Shell实现八大排序算法

使用Shell脚本实现八大排序算法可以是一个有趣的挑战。虽然Shell脚本不是专门设计用于高效排序的编程语言，但它可以用来演示基本的排序算法。以下是八大排序算法的Shell实现：

1. 冒泡排序 (Bubble Sort)

bubble_sort() {arr=("$@")n=${#arr[@]}for ((i = 0; i < n; i++)); dofor ((j = 0; j < n - i - 1; j++)); doif ((arr[j] > arr[j + 1])); thentemp=${arr[j]}arr[j]=${arr[j + 1]}arr[j + 1]=$tempfidonedoneecho "${arr[@]}"
}

2. 选择排序 (Selection Sort)

selection_sort() {arr=("$@")n=${#arr[@]}for ((i = 0; i < n - 1; i++)); domin_idx=$ifor ((j = i + 1; j < n; j++)); doif ((arr[j] < arr[min_idx])); thenmin_idx=$jfidonetemp=${arr[i]}arr[i]=${arr[min_idx]}arr[min_idx]=$tempdoneecho "${arr[@]}"
}

3. 插入排序 (Insertion Sort)

insertion_sort() {arr=("$@")n=${#arr[@]}for ((i = 1; i < n; i++)); dokey=${arr[i]}j=$((i - 1))while ((j >= 0 && arr[j] > key)); doarr[j + 1]=${arr[j]}j=$((j - 1))donearr[j + 1]=$keydoneecho "${arr[@]}"
}

4. 归并排序 (Merge Sort)

merge_sort() {arr=("$@")if [ ${#arr[@]} -le 1 ]; thenecho "${arr[@]}"returnfimid=$(( ${#arr[@]} / 2 ))left=($(merge_sort "${arr[@]:0:$mid}"))right=($(merge_sort "${arr[@]:$mid}"))merged=()while [ ${#left[@]} -gt 0 ] && [ ${#right[@]} -gt 0 ]; doif [ ${left[0]} -le ${right[0]} ]; thenmerged+=("${left[0]}")left=("${left[@]:1}")elsemerged+=("${right[0]}")right=("${right[@]:1}")fidoneecho "${merged[@]} ${left[@]} ${right[@]}"
}

5. 快速排序 (Quick Sort)

quick_sort() {arr=("$@")if [ ${#arr[@]} -le 1 ]; thenecho "${arr[@]}"returnfipivot=${arr[0]}left=()right=()for ((i = 1; i < ${#arr[@]}; i++)); doif [ ${arr[i]} -lt $pivot ]; thenleft+=("${arr[i]}")elseright+=("${arr[i]}")fidoneleft_sorted=($(quick_sort "${left[@]}"))right_sorted=($(quick_sort "${right[@]}"))echo "${left_sorted[@]} $pivot ${right_sorted[@]}"
}

6. 希尔排序 (Shell Sort)

shell_sort() {arr=("$@")n=${#arr[@]}gap=$((n / 2))while [ $gap -gt 0 ]; dofor ((i = gap; i < n; i++)); dotemp=${arr[i]}j=$iwhile ((j >= gap && arr[j - gap] > temp)); doarr[j]=${arr[j - gap]}j=$((j - gap))donearr[j]=$tempdonegap=$((gap / 2))doneecho "${arr[@]}"
}

7. 堆排序 (Heap Sort)

heapify() {arr=("$@")n=$1i=$2largest=$ileft=$((2 * i + 1))right=$((2 * i + 2))if ((left < n && arr[left] > arr[largest])); thenlargest=$leftfiif ((right < n && arr[right] > arr[largest])); thenlargest=$rightfiif ((largest != i)); thentemp=${arr[i]}arr[i]=${arr[largest]}arr[largest]=$temparr=($(heapify $n $largest "${arr[@]}"))fiecho "${arr[@]}"
}heap_sort() {arr=("$@")n=${#arr[@]}for ((i = n / 2 - 1; i >= 0; i--)); doarr=($(heapify $n $i "${arr[@]}"))donefor ((i = n - 1; i > 0; i--)); dotemp=${arr[0]}arr[0]=${arr[i]}arr[i]=$temparr=($(heapify $i 0 "${arr[@]}"))doneecho "${arr[@]}"
}

8. 计数排序 (Counting Sort)

counting_sort() {arr=("$@")n=${#arr[@]}max=${arr[0]}for ((i = 1; i < n; i++)); doif ((arr[i] > max)); thenmax=${arr[i]}fidonecount=( $(for ((i = 0; i <= max; i++)); do echo 0; done) )for ((i = 0; i < n; i++)); do((count[arr[i]]++))doneindex=0for ((i = 0; i <= max; i++)); dowhile ((count[i] > 0)); doarr[index]=$i((index++))((count[i]--))donedoneecho "${arr[@]}"
}

示例运行

假设我们要对数组 3 6 8 10 1 2 1 进行排序，可以这样调用上述的每个函数：

array=(3 6 8 10 1 2 1)echo "Bubble Sort:"
bubble_sort "${array[@]}"echo "Selection Sort:"
selection_sort "${array[@]}"echo "Insertion Sort:"
insertion_sort "${array[@]}"echo "Merge Sort:"
merge_sort "${array[@]}"echo "Quick Sort:"
quick_sort "${array[@]}"echo "Shell Sort:"
shell_sort "${array[@]}"echo "Heap Sort:"
heap_sort "${array[@]}"echo "Counting Sort:"
counting_sort "${array[@]}"

这些Shell脚本实现了八大排序算法的基本功能，可以在命令行中运行，展示排序过程的基本原理。

四、DFS和BFS应用场景

深度优先搜索（DFS）和广度优先搜索（BFS）在不同的应用场景中各有优势和适用性。以下是它们在不同场景中的具体应用：

深度优先搜索（DFS）

1. 路径查找
  • 迷宫求解: 寻找从入口到出口的路径。
  • 连通性问题: 检查图中的所有连通分量。
  • 拓扑排序: 有向无环图的拓扑排序。
  • 解决递归问题: 例如解决数独、八皇后问题等。
2. 图的遍历
  • 全路径搜索: 找到图中所有可能的路径，适用于全排列、组合等问题。
  • 图的连通分量: 查找图中所有连通分量，应用于社交网络分析等。
3. 树的操作
  • 子树匹配: 查找树中是否存在一个与给定子树匹配的子树。
  • 树的深度: 计算树的最大深度或高度。
4. 动态规划
  • 记忆化搜索: 使用递归和记忆化的方法解决复杂问题，例如背包问题。
5. 状态空间搜索
  • 解决搜索问题: 如游戏AI、机器人路径规划。

广度优先搜索（BFS）

1. 最短路径查找
  • 无权图的最短路径: 在无权图中找到从起点到终点的最短路径，例如社交网络中的最短关系链、棋盘上的最短路径等。
  • 迷宫最短路径: 在迷宫中找到最短路径。
2. 层次遍历
  • 树的层次遍历: 在树中按层次逐层遍历节点，应用于序列化和反序列化二叉树、打印树的层次结构等。
  • 图的层次遍历: 用于解决最短路径、网络传播、拓扑层次结构等问题。
3. 状态空间搜索
  • 广度优先搜索问题: 例如解决数独、拼图等问题，适用于需要找到最小步骤解的场景。
4. 网络流
  • 最大流问题: 使用BFS找到增广路径，实现Edmonds-Karp算法。
5. 多源点多终点问题
  • 多源BFS: 从多个起点同时开始搜索，例如火焰蔓延问题。

总结

  • DFS适用于需要探索所有可能路径的场景，或者当你需要深度搜索解决问题时，例如全路径搜索、连通性检测、树的遍历等。
  • BFS适用于需要找到最短路径或者层次遍历的场景，例如无权图的最短路径、层次遍历、最小步骤解等。

两种算法各有其优点，选择哪种算法取决于具体问题的性质和要求。

五、SHELL实现深度和广度优先算法

深度优先搜索（DFS）和广度优先搜索（BFS）是两种基本的图遍历算法。它们的主要区别在于遍历顺序和使用的数据结构。以下是它们的原理简介及Shell实现。

深度优先搜索（DFS）

原理简介

DFS从起始节点开始，沿着一个分支一直深入到不能再深入为止，然后回溯到上一个节点，再从未访问的分支继续深入，直到所有节点都被访问。DFS使用栈（Stack）数据结构，可以通过递归或显式使用栈实现。

Shell实现

由于Shell脚本不直接支持递归调用，这里用显式栈实现DFS。

#!/bin/bash# 深度优先搜索 (DFS)
dfs() {local node=$1local visited=$2local stack=()# 使用栈进行DFSstack+=($node)while [ ${#stack[@]} -ne 0 ]; donode=${stack[-1]}stack=("${stack[@]:0:${#stack[@]}-1}")if [[ $visited =~ $node ]]; thencontinuefivisited+="$node "echo "Visited: $node"for neighbor in $(echo ${graph[$node]} | tr "," "\n"); dostack+=($neighbor)donedone
}# 示例图表示为关联数组
declare -A graph
graph["A"]="B,C"
graph["B"]="A,D,E"
graph["C"]="A,F"
graph["D"]="B"
graph["E"]="B,F"
graph["F"]="C,E"visited=""
dfs "A" "$visited"

广度优先搜索（BFS）

原理简介

BFS从起始节点开始，先访问所有邻居节点，然后逐层向外扩展，直到所有节点都被访问。BFS使用队列（Queue）数据结构。

Shell实现
#!/bin/bash# 广度优先搜索 (BFS)
bfs() {local node=$1local visited=""local queue=()# 使用队列进行BFSqueue+=($node)while [ ${#queue[@]} -ne 0 ]; donode=${queue[0]}queue=("${queue[@]:1}")if [[ $visited =~ $node ]]; thencontinuefivisited+="$node "echo "Visited: $node"for neighbor in $(echo ${graph[$node]} | tr "," "\n"); doqueue+=($neighbor)donedone
}# 示例图表示为关联数组
declare -A graph
graph["A"]="B,C"
graph["B"]="A,D,E"
graph["C"]="A,F"
graph["D"]="B"
graph["E"]="B,F"
graph["F"]="C,E"bfs "A"

总结

  • DFS：利用栈结构（递归或显式栈），优先深入到树的最深处再回溯。适用于需要完全遍历所有路径的情况。
  • BFS：利用队列结构，逐层向外扩展，适用于寻找最短路径和广度优先遍历的情况。

这两种算法在Shell脚本中的实现通过显式栈和队列操作完成，虽然Shell脚本不如其他编程语言高效，但它们的逻辑和工作原理相同。

完。

希望对您有用！关注锅总，可及时获得更多运维实用操作！

相关文章：

  • 如何修复“AI的原罪”
  • 甘肃旅游服务平台的设计
  • 【网络安全学习】漏洞扫描：-04- ZAP漏洞扫描工具
  • Harbor本地仓库搭建003_Harbor常见错误解决_以及各功能使用介绍_镜像推送和拉取---分布式云原生部署架构搭建003
  • 第7章：系统架构设计基础知识-软件架构风格
  • 02 Shell编程之条件语句
  • 【第26章】Vue实战篇之用户信息修改
  • C++(26): 原子操作（std::atomic）
  • 诺瓦星云入职认知能力SHL测验Verify职业性格问卷OPQ可搜索带解析求职题库
  • Java练习题4
  • 锂锗磷硫（LGPS）是代表性硫化物固态电解质产品之一 技术研究不断深入
  • python-题库篇-Python语言特性
  • 【计算机毕业设计】196运动健康weixin小程序
  • leetcode 动态规划（基础版）三角形最小路径和
  • JC/T 2752-2023 导（防）静电不发火地坪检测
  • 【刷算法】求1+2+3+...+n
  • Git学习与使用心得（1）—— 初始化
  • java架构面试锦集：开源框架+并发+数据结构+大企必备面试题
  • leetcode386. Lexicographical Numbers
  • Linux下的乱码问题
  • Mysql优化
  • PHP的类修饰符与访问修饰符
  • 聊聊directory traversal attack
  • 批量截取pdf文件
  • 嵌入式文件系统
  • 如何选择开源的机器学习框架？
  • 数据库写操作弃用“SELECT ... FOR UPDATE”解决方案
  • 王永庆：技术创新改变教育未来
  • 微信小程序设置上一页数据
  • 写给高年级小学生看的《Bash 指南》
  • 一道面试题引发的“血案”
  • 运行时添加log4j2的appender
  • “十年磨一剑”--有赞的HBase平台实践和应用之路 ...
  • PostgreSQL之连接数修改
  • Prometheus VS InfluxDB
  • #laravel部署安装报错loadFactoriesFrom是undefined method #
  • #每天一道面试题# 什么是MySQL的回表查询
  • （11）MATLAB PCA+SVM 人脸识别
  • （ISPRS，2023）深度语义-视觉对齐用于zero-shot遥感图像场景分类
  • （附源码）php投票系统 毕业设计 121500
  • （附源码）ssm高校志愿者服务系统 毕业设计 011648
  • （十） 初识 Docker file
  • .gitignore文件使用
  • .NET Core6.0 MVC+layui+SqlSugar 简单增删改查
  • .net反混淆脱壳工具de4dot的使用
  • .net开发引用程序集提示没有强名称的解决办法
  • .NET中两种OCR方式对比
  • .pyc文件还原.py文件_Python什么情况下会生成pyc文件？
  • .vimrc 配置项
  • @RequestBody与@ModelAttribute
  • @Transactional 竟也能解决分布式事务？
  • [ CTF ] WriteUp-2022年春秋杯网络安全联赛-冬季赛
  • [20140403]查询是否产生日志
  • [2669]2-2 Time类的定义
  • [acwing周赛复盘] 第 94 场周赛20230311