AI 助理
备案控制台登录注册
开发者社区 华章出版社 文章 正文

《计算复杂性：现代方法》——1.3　效率和运行时间

2017-05-02 1415
版权
举报
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介：

本节书摘来自华章计算机《计算复杂性：现代方法》一书中的第1章，第1.3节，作者 ［美］桑杰夫·阿罗拉（Sanjeev Arora），博阿兹·巴拉克（Boaz Barak），译 骆吉洲，更多章节内容可以访问云栖社区“华章计算机”公众号查看。

1.3　效率和运行时间

现在，我们将运行时间的概念形式化。由于即便是最平凡的计算任务也需要读取输入，因此把执行的基本操作的个数表达为输入长度的函数，该函数可以定义为运行时间。

screenshot

时间可构造函数

screenshot

1.3.1　定义的健壮性

screenshot
screenshot
screenshot
screenshot
screenshot
screenshot

华章计算机
+关注
10051文章
目录
打赏
0
0
0
0
1408
分享
相关文章
大树营养快线
|
4月前
|
存储 监控 算法
在进行精度控制时，如何避免舍入误差的累积？
【10月更文挑战第29天】通过选择合适的精度控制方法、优化计算顺序和方式、运用误差补偿技术以及建立数据验证与监控机制等多种手段的综合运用，可以有效地避免舍入误差的累积，提高计算结果的精度和可靠性，满足各种对精度要求较高的应用场景的需求。
大树营养快线
173 3
游客ocguhxjgzndzq
|
2天前
|
机器学习/深度学习 存储 人工智能
Attention优化重大突破！显存减半效率倍增
本文探讨了Transformer中Attention机制的演变与优化。从2017年Transformer提出以来，各种改进如MQA、GQA、MLA等层出不穷，旨在降低计算复杂度和显存消耗，同时保持模型性能。文章首先介绍了Attention的基本原理，通过QKV矩阵运算实现序列建模。接着分析了优化方法：kv caching将计算复杂度从O(n^3)降至O(n^2)，但带来显存压力；MQA、GQA等通过减少或压缩K/V降低显存需求；而NSV、MoBA等稀疏化研究进一步缓解长序列下的计算与存储负担，推动大模型向更长上下文扩展。
游客ocguhxjgzndzq
10 1
游客qeoynko2nmbgk
|
6月前
|
算法 C++
如何精确计算出一个算法的CPU运行时间?
如何精确计算出一个算法的CPU运行时间?
游客qeoynko2nmbgk
83 0
楠竹11
|
9月前
偏微分方程有了基础模型：样本需求数量级减少，14项任务表现最佳
【6月更文挑战第16天】研究人员提出Poseidon模型，减少求解偏微分方程（PDEs）的样本需求，提升效率。在15个挑战任务中，该模型在14项表现最优。基于scOT的多尺度架构， Poseidon降低了计算成本，但仍有泛化和资源限制。[论文链接](https://arxiv.org/pdf/2405.19101)**
楠竹11
118 4
楠竹11
|
10月前
|
人工智能
小模型性能饱和、表现不佳，根源是因为Softmax?
【5月更文挑战第15天】研究人员发现小型语言模型性能受限于Softmax瓶颈，即隐藏维度与目标上下文概率分布不匹配，导致模型在预测时表现不佳。通过实验，他们证实小于1000个隐藏维度的模型易在训练后期出现退化表示，影响性能。该发现为改进小模型性能提供了新视角，但需要更多后续研究验证。[[240 characters]]
楠竹11
90 1
配电网和matlab
|
移动开发 安全 数据挖掘
(文章复现)梯级水光互补系统最大化可消纳电量期望短期优化调度模型matlab代码
参考文献： [1]罗彬,陈永灿,刘昭伟等.梯级水光互补系统最大化可消纳电量期望短期优化调度模型[J].电力系统自动化,2023,47(10):66-75.
配电网和matlab
302 0
vohelon
|
Serverless
函数计算减少冷启动对性能的影响
函数计算减少冷启动对性能的影响
vohelon
393 1
游客iigf2m33ba53k
|
存储 传感器 机器学习/深度学习
V2X会是未来趋势吗？看看这种轻量级方法，大幅降低碰撞概率！
本文提出了一种Ledger概念，它通过Ledger信息的广播，在一个资源预留区间(RRI)内向网络中的每辆车传递碰撞信息。碰撞车辆知道它已经与其他车辆相撞，并将在下一个 SPS 期间重新选择。除此之外，其他协议都遵循 SPS。通过引入 Ledger，虽然牺牲了14.29% 的资源，但最终可以降低碰撞概率。本文使用蒙特卡罗模拟器对Ledger系统的性能进行了验证和分析。数值结果表明，遵循 SPS 协议，Ledger 系统可以使碰撞概率在一定数量 RRI 后收敛到零。
游客iigf2m33ba53k
201 0
V2X会是未来趋势吗？看看这种轻量级方法，大幅降低碰撞概率！
码匠
|
算法
分析复杂度来判断算法效率
算法复杂度用于分析算法运行所需计算机资源的量，需要的时间资源为时间复杂度，需要的空间资源为空间复杂度。 在判断一个算法的优劣时，可以抛开软件和硬件因素，只考虑问题的规模。编写程序前预先估计算法优劣，可以改进并选择更高效的算法。
码匠
180 0
分析复杂度来判断算法效率
红目香薰
|
C#
C#计算两个时间的差
.NET
红目香薰
153 0
C#计算两个时间的差

华章出版社
+ 订阅

热门文章

最新文章

  • 1
    YARN中的CPU资源隔离-CGroups
    6235
  • 2
    阿里云全面支持IPv6！一文揽尽4位大咖精彩演讲
    8269
  • 3
    OAuth 及 移动端鉴权调研
    8
  • 4
    SQL0286N. DB2表空间的pagesize问题
    8437
  • 5
    3大阶段，30+教程，超全年度 Python 礼包大放送 | 技术日报（15期）
    2
  • 6
    Node.js 要完了吗？
    696
  • 7
    异或交换两个数的值
    598
  • 8
    mysql命令行修改字符编码
    1
  • 9
    第七章 ping程序
    3
  • 10
    C++ 实用的小程序
    508
  • 1
    算法系列之回溯算法求解数独及所有可能解
    33
  • 2
    《AI算法训练困境求解：深挖鸿蒙系统资源优势》
    22
  • 3
    《鸿蒙系统中人工智能驱动的智能助手：应用模式与未来航向》
    32
  • 4
    《深度剖析：将先进语音识别技术融入鸿蒙系统AI应用》
    29
  • 5
    《深入剖析：鸿蒙开发工具模拟器在人工智能应用模拟测试中的特性与局限》
    25
  • 6
    《解锁华为黑科技：MindSpore+鸿蒙深度集成奥秘》
    23
  • 7
    vue中npm打包遇到× eslint —fix found some errors. Please fix them and try committing again.husky > pre-commit hook failed (add —no-verify to bypass)报错解决方案-卓伊凡
    21
  • 8
    这个多模态智能体，让电力装备运维越来越“聪明”
    43
  • 9
    Termux安卓终端美化与开发实战：从下载到插件优化，小白也能玩转Linux
    44
  • 10
    Linux 手动安装快速部署 LNMP 环境实战
    45

    • 相关电子书

    更多
  • 恒逸石化：用计算消耗取代能源消耗
  • 恒逸石化 -用计算消耗取代能源消耗
  • 《更快更稳更安全》
    • 下一篇
    获取百炼API-KEY
    目录
    AI助理

    你好，我是AI助理

    可以解答问题、推荐解决方案等