2.4.5 线性对数算法的性能
性能指标很好地描述了同类算法的共同行为。为了更好地阐述算法在实践中的行为，我们定义了一个函数t(n)，用于表示算法解决样本规模为n的问题所需要的时间。分治法是解决问题的一个高效方法，它将规模为n的问题划分成（大致相等的）两个规模为n/2的子问题，并通过递归解决问题。这些子问题会通过线性时间方式合并在一起来解决原先规模为n的问题。使用数学表达式可以表示为：
也就是说，t(n)包括了解决两个子问题和归并结果的费用，其中归并结果的费用不超过线性时间（即c*n）。在等式的右边，t(n/2)是解决规模为n/2 的问题的时间，按此逻辑推理，t(n/2)可以表示为：
所以最初的等式可以写为：
如果再扩展一层，可以得到：
《算法技术手册》一2.4.5 线性对数算法的性能
2017-09-07
1136
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《
阿里云开发者社区用户服务协议》和
《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写
侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介：
本节书摘来华章计算机《算法技术手册》一书中的第2章 ，第2.4.5节， George T.Heineman Gary Pollice
Stanley Selkow 著
杨晨 曹如进 译 译更多章节内容可以访问云栖社区“华章计算机”公众号查看。
目录
相关文章
|
1月前
|
存储
弹性计算
算法
倚天产品介绍|倚天ECS加速国密算法性能
倚天ECS是阿里云基于平头哥自研数据中心芯片倚天710推出arm架构实例，采用armv9架构，支持SM3/SM4指令，可以加速国密算法性能。本文基于OpenSSL 3.2和Tongsuo 实测对比了倚天ECS g8y实例和Intel g7 实例国密性能。为用户选择ECS提供参考。
95
0
1
|
2月前
|
算法
测试技术
C++
|
2月前
|
机器学习/深度学习
自然语言处理
算法
|
8天前
|
算法
|
1月前
|
机器学习/深度学习
算法
计算机视觉
利用深度学习算法实现图像风格转换技术探究
本文将通过深入分析深度学习算法在图像处理领域的应用，探讨如何利用神经网络实现图像风格转换技术。通过研究不同风格迁移算法的原理和实现方式，揭示其在艺术创作、图像编辑等领域的潜在应用和挑战。
28
14
14
|
2月前
|
存储
算法
Java
|
2月前
|
存储
算法
搜索推荐
掌握数据结构与算法，成为技术大牛
数据结构与算法是计算机科学中至关重要的基础知识，它们的应用贯穿于各种编程语言和技术领域。本文将介绍数据结构与算法的基本概念及其在实际开发中的应用，帮助读者打下坚实的技术基础，成为真正的技术大牛。
37
4
4
|
2月前
|
算法
安全
Java
|
2月前
|
算法
Java
|
3月前
|
存储
安全
算法
保护数据隐私的安全加密算法：技术守护个人信息安全的利器
在数字化时代，个人信息安全日益受到威胁。本文将深入探讨安全加密算法的重要性，以及如何利用先进的技术保护个人数据的隐私。从对称加密到非对称加密，再到现代密码学的发展，我们将一一解析这些技术的原理和应用。通过了解安全加密算法，我们可以更好地保护个人数据隐私，确保信息的安全传输和存储。
63
3
3
热门文章
最新文章
1
【MATLAB】GA_ELM神经网络时序预测算法
2
RPN(Region Proposal Networks)候选区域网络算法解析（附PyTorch代码）
3
使用Python实现DBSCAN聚类算法
4
【软件设计师备考 专题 】算法探索：排序、查找、数值计算和字符串处理（一）
5
【C++ 数据结构与算法 一站式备考指南】一文掌握 数据结构与算法课程 知识点（二）
6
R语言聚类算法的应用实例
7
Java数据结构与算法-java数据结构与算法（二）
8
深度思考：雪花算法snowflake分布式id生成原理详解
9
【软件设计师备考 专题 】深入理解数据压缩、递归和图的相关算法
10
【C++ 数据结构与算法 一站式备考指南】一文掌握 数据结构与算法课程 知识点（一）
1
软件体系结构 - 调度算法(3) 单调速率调度算法
16
2
【视频】Copula算法原理和R语言股市收益率相依性可视化分析-1
16
3
对称密钥加密算法和公开密钥加密算法有什么区别
19
4
基于DCT和扩频的音频水印嵌入提取算法matlab仿真
18
5
双指针（基础算法题）
9
6
代码随想录算法训练营第六十天 | LeetCode 84. 柱状图中最大的矩形
18
7
代码随想录算法训练营第五十七天 | LeetCode 739. 每日温度、496. 下一个更大元素 I
11
8
代码随想录算法训练营第五十六天 | LeetCode 647. 回文子串、516. 最长回文子序列、动态规划总结
26
9
分布式(计算机算法)
24
10
贪心算法(被黑心公司强迫写的降薪算法)
11