搜索

[22729] 2014-06-02_主宰这个世界的10种算法

文档创建者：s7ckTeam
浏览次数：7
最后更新：2025-01-18
2014-06-02_主宰这个世界的10种算法 主 宰 这 个 世 界 的 1 0 种 算 法 L i n u x 中 国   2 0 1 4 - 0 6 - 0 2 R e d d i t 有 篇 帖 子 介 绍 了 算 法 对 我 们 现 在 生 活 的 重 要 性 ， 以 及 哪 些 算 法 对 现 代 文 明 所 做 贡 献 最 大 。 如 果 对 算 法 有 所 了 解 ， 读 这 篇 文 章 时 你 可 能 会 问 “ 作 者 知 道 算 法 为 何 物 吗 ？ ” ， 或 是 “ F a c e b o o k 的 ‘ 信 息 流 ’ ( N e w s   F e e d ) 算 是 一 种 算 法 吗 ？ ” ， 如 果 “ 信 息 流 ” 是 算 法 ， 那 就 可 以 把 所 有 事 物 都 归 结 为 一 种 算 法 。 才 疏 学 浅 ， 结 合 那 篇 帖 子 ， 接 下 来 我 试 着 解 释 一 下 算 法 是 什 么 ， 又 是 哪 1 0 个 算 法 正 在 主 导 我 们 的 世 界 。 什 么 是 算 法 ？ 简 而 言 之 ， 任 何 定 义 明 确 的 计 算 步 骤 都 可 称 为 算 法 ， 接 受 一 个 或 一 组 值 为 输 入 ， 输 出 一 个 或 一 组 值 。 ( 来 源 ： h o m a s   H .   C o r m e n ,   C h a l e s   E . L e i s e r s o n   《 算 法 导 论 第 3 版 》 ) 可 以 这 样 理 解 ， 算 法 是 用 来 解 决 特 定 问 题 的 一 系 列 步 骤 ( 不 仅 计 算 机 需 要 算 法 ， 我 们 在 日 常 生 活 中 也 在 使 用 算 法 ) 。 算 法 必 须 具 备 如 下 3 个 重 要 特 性 ： [ 1 ]   有 穷 性 。 执 行 有 限 步 骤 后 ， 算 法 必 须 中 止 。 [ 2 ]   确 切 性 。 算 法 的 每 个 步 骤 都 必 须 确 切 定 义 。 [ 3 ]   可 行 性 。 特 定 算 法 须 可 以 在 特 定 的 时 间 内 解 决 特 定 问 题 ， 其 实 ， 算 法 虽 然 广 泛 应 用 在 计 算 机 领 域 ， 但 却 完 全 源 自 数 学 。 实 际 上 ， 最 早 的 数 学 算 法 可 追 溯 到 公 元 前 1 6 0 0 年 - B a b y l o n i a n s 有 关 求 因 式 分 解 和 平 方 根 的 算 法 。 那 么 又 是 哪 1 0 个 计 算 机 算 法 造 就 了 我 们 今 天 的 生 活 呢 ？ 请 看 下 面 的 表 单 ， 排 名 不 分 先 后 ： 1 .   归 并 排 序 ( M E R G E   S O R T ) ， 快 速 排 序 ( Q U I C K   S O R T ) 和 堆 积 排 序 ( H E A P   S O R T )
哪 个 排 序 算 法 效 率 最 高 ？ 这 要 看 情 况 。 这 也 就 是 我 把 这 3 种 算 法 放 在 一 起 讲 的 原 因 ， 可 能 你 更 常 用 其 中 一 种 ， 不 过 它 们 各 有 千 秋 。 归 并 排 序 算 法 ， 是 目 前 为 止 最 重 要 的 算 法 之 一 ， 是 分 治 法 的 一 个 典 型 应 用 ， 由 数 学 家 J o h n   v o n   N e u m a n n 于 1 9 4 5 年 发 明 。 快 速 排 序 算 法 ， 结 合 了 集 合 划 分 算 法 和 分 治 算 法 ， 不 是 很 稳 定 ， 但 在 处 理 随 机 列 阵 ( A M - b a s e d   a r r a y s ) 时 效 率 相 当 高 。 堆 积 排 序 ， 采 用 优 先 伫 列 机 制 ， 减 少 排 序 时 的 搜 索 时 间 ， 同 样 不 是 很 稳 定 。 与 早 期 的 排 序 算 法 相 比 ( 如 冒 泡 算 法 ) ， 这 些 算 法 将 排 序 算 法 提 上 了 一 个 大 台 阶 。 也 多 亏 了 这 些 算 法 ， 才 有 今 天 的 数 据 发 掘 ， 人 工 智 能 ， 链 接 分 析 ， 以 及 大 部 分 网 页 计 算 工 具 。 2 .   傅 立 叶 变 换 和 快 速 傅 立 叶 变 换 这 两 种 算 法 简 单 ， 但 却 相 当 强 大 ， 整 个 数 字 世 界 都 离 不 开 它 们 ， 其 功 能 是 实 现 时 间 域 函 数 与 频 率 域 函 数 之 间 的 相 互 转 化 。 能 看 到 这 篇 文 章 ， 也 是 托 这 些 算 法 的 福 。 因 特 网 ， W I F I ， 智 能 机 ， 座 机 ， 电 脑 ， 路 由 器 ， 卫 星 等 几 乎 所 有 与 计 算 机 相 关 的 设 备 都 或 多 或 少 与 它 们 有 关 。 不 会 这 两 种 算 法 ， 你 根 本 不 可 能 拿 到 电 子 ， 计 算 机 或 者 通 信 工 程 学 位 。 ( U S A ) 3 . 代 克 思 托 演 算 法   ( D i j k s t r a ' s   a l g o r i t h m ) 可 以 这 样 说 ， 如 果 没 有 这 种 算 法 ， 因 特 网 肯 定 没 有 现 在 的 高 效 率 。 只 要 能 以 “ 图 ” 模 型 表 示 的 问 题 ， 都 能 用 这 个 算 法 找 到 “ 图 ” 中 两 个 节 点 间 的 最 短 距 离 。 虽 然 如 今 有 很 多 更 好 的 方 法 来 解 决 最 短 路 径 问 题 ， 但 代 克 思 托 演 算 法 的 稳 定 性 仍 无 法 取 代 。 4 .   R S A 非 对 称 加 密 算 法
毫 不 夸 张 地 说 ， 如 果 没 有 这 个 算 法 对 密 钥 学 和 网 络 安 全 的 贡 献 ， 如 今 因 特 网 的 地 位 可 能 就 不 会 如 此 之 高 。 现 在 的 网 络 毫 无 安 全 感 ， 但 遇 到 钱 相 关 的 问 题 时 我 们 必 需 要 保 证 有 足 够 的 安 全 感 ， 如 果 你 觉 得 网 络 不 安 全 ， 肯 定 不 会 傻 乎 乎 地 在 网 页 上 输 入 自 己 的 银 行 卡 信 息 。 R S A 算 法 ， 密 钥 学 领 域 最 牛 叉 的 算 法 之 一 ， 由 R S A 公 司 的 三 位 创 始 人 提 出 ， 奠 定 了 当 今 的 密 钥 研 究 领 域 。 用 这 个 算 法 解 决 的 问 题 简 单 又 复 杂 ： 保 证 安 全 的 情 况 下 ， 如 何 在 独 立 平 台 和 用 户 之 间 分 享 密 钥 。 5 .   哈 希 安 全 算 法 ( S e c u r e   H a s h   A l g o r i t h m ) 确 切 地 说 ， 这 不 是 一 种 算 法 ， 而 是 一 组 加 密 哈 希 函 数 ， 由 美 国 国 家 标 准 技 术 研 究 所 首 先 提 出 。 无 论 是 你 的 应 用 商 店 ， 电 子 邮 件 和 杀 毒 软 件 ， 还 是 浏 览 器 等 等 ， 都 使 用 这 种 算 法 来 保 证 你 正 常 下 载 ， 以 及 是 否 被 “ 中 间 人 攻 击 ” ， 或 者 “ 网 络 钓 鱼 ” 。 6 .   整 数 质 因 子 分 解 算 法 ( I n t e g e r   f a c t o r i z a t i o n ) 这 其 实 是 一 个 数 学 算 法 ， 不 过 已 经 广 泛 应 用 与 计 算 机 领 域 。 如 果 没 有 这 个 算 法 ， 加 密 信 息 也 不 会 如 此 安 全 。 通 过 一 系 列 步 骤 将 ， 它 可 以 将 一 个 合 成 数 分 解 成 不 可 再 分 的 数 因 子 。 很 多 加 密 协 议 都 采 用 了 这 个 算 法 ， 就 比 如 刚 提 到 的 R S A 算 法 。 7 .   链 接 分 析 算 法 ( L i n k   A n a l y s i s ) 在 因 特 网 时 代 ， 不 同 入 口 间 关 系 的 分 析 至 关 重 要 。 从 搜 索 引 擎 和 社 交 网 站 ， 到 市 场 分 析 工 具 ， 都 在 不 遗 余 力 地 寻 找 因 特 网 的 正 真 构 造 。 链 接 分 析 算 法 一 直 是 这 个 领 域 最 让 人 费 解 的 算 法 之 一 ， 实 现 方 式 不 一 ， 而 且 其 本 身 的 特 性 让 每 个 实 现 方 式 的 算 法 发 生 异 化 ， 不 过 基 本 原 理 却 很 相 似 。 链 接 分 析 算 法 的 机 制 其 实 很 简 单 ： 你 可 以 用 矩 阵 表 示 一 幅 “ 图 “ ， 形 成 本 征 值 问 题 。 本 征 值 问 题 可 以 帮 助 你 分 析 这 个 “ 图 ” 的 结 构 ， 以 及 每 个 节 点 的 权 重 。 这 个 算 法 于 1 9 7 6 年 由 G a b r i e l   P i n s k i 和 F r a n c i s   N a r i n 提 出 。 谁 会 用 这 个 算 法 呢 ？ G o o g l e 的 网 页 排 名 ， F a c e b o o k 向 你 发 送 信 息 流 时 ( 所 以 信 息 流 不 是 算 法 ， 而 是 算 法 的 结 果 ) ， G o o g l e + 和 F a c e b o o k 的 好 友 推 荐 功 能 ， L i n k e d I n 的 工 作 推 荐 ， Y o u t u b e 的 视 频 推 荐 ， 等 等 。 普 遍 认 为 G o o g l e 是 首 先 使 用 这 类 算 法 的 机 构 ， 不 过 其 实 早 在 1 9 9 6 年 ( G o o g l e 问 世 2 年 前 ) 李 彦 宏 就 创 建 的 “ R a n k D e x ” 小 型 搜 索 引 擎 就 使 用 了 这 个 思 路 。 而 H y p e r   S e a r c h 搜 索 算 法 建 立 者 马 西 莫 · 马 奇 奥 里 也 曾 使 用 过 类 似 的 算 法 。 这 两 个 人 都 后 来 都 成 为 了 G o o g l e 历 史 上 的 传 奇 人 物 。
8 .   比 例 微 积 分 算 法 ( P r o p o r t i o n a l   I n t e g r a l   D e r i v a t i v e   A l g o r i t h m ) 飞 机 ， 汽 车 ， 电 视 ， 手 机 ， 卫 星 ， 工 厂 和 机 器 人 等 等 事 物 中 都 有 这 个 算 法 的 身 影 。 简 单 来 讲 ， 这 个 算 法 主 要 是 通 过 “ 控 制 回 路 反 馈 机 制 ” ， 减 小 预 设 输 出 信 号 与 真 实 输 出 信 号 间 的 误 差 。 只 要 需 要 信 号 处 理 ， 或 电 子 系 统 来 控 制 自 动 化 机 械 ， 液 压 和 加 热 系 统 ， 都 需 要 用 到 这 个 算 个 法 。 没 有 它 ， 就 没 有 现 代 文 明 。 9 .   数 据 压 缩 算 法 数 据 压 缩 算 法 有 很 多 种 ， 哪 种 最 好 ？ 这 要 取 决 于 应 用 方 向 ， 压 缩 m p 3 ， J P E G 和 M P E G - 2 文 件 都 不 一 样 。 哪 里 能 见 到 它 们 ？ 不 仅 仅 是 文 件 夹 中 的 压 缩 文 件 。 你 正 在 看 的 这 个 网 页 就 是 使 用 数 据 压 缩 算 法 将 信 息 下 载 到 你 的 电 脑 上 。 除 文 字 外 ， 游 戏 ， 视 频 ， 音 乐 ， 数 据 储 存 ， 云 计 算 等 等 都 是 。 它 让 各 种 系 统 更 轻 松 ， 效 率 更 高 。 1 0 .   随 机 数 生 成 算 法 到 如 今 ， 计 算 机 还 没 有 办 法 生 成 “ 真 正 的 ” 随 机 数 ， 但 伪 随 机 数 生 成 算 法 就 足 够 了 。 这 些 算 法 在 许 多 领 域 都 有 应 用 ， 如 网 络 连 接 ， 加 密 技 术 ， 安 全 哈 希 算 法 ， 网 络 游 戏 ， 人 工 智 能 ， 以 及 问 题 分 析 中 的 条 件 初 始 化 。 这 个 表 单 并 不 完 整 ， 很 多 与 我 们 密 切 相 关 的 算 法 都 没 有 提 到 ， 如 机 器 学 习 和 矩 阵 乘 法 。 另 外 ， 知 识 有 限 ， 如 有 批 漏 ， 还 望 指 正 。 [ c l a u d i o   v i a   m e d i u m . c o m ] 本 文 地 址 ： h t t p : / / l i n u x . c n / a r t i c l e - 3 1 2 5 - 1 . h t m l
阅 读 原 文
回复

举报

高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

使用Markdown编辑器编辑 使用富文本编辑器编辑

Archiver| 手机版| 小黑屋|
Powered by Discuz! X3.4 Copyright © 2001-2020, Tencent Cloud. 商业源码建议获取授权，如侵犯您的权益，请联系客服处理