《算法技术手册》一2.3.4 上下界

简介: 本节书摘来华章计算机《算法技术手册》一书中的第2章 ,第2.3.4节, George T.Heineman Gary Pollice Stanley Selkow 著 杨晨 曹如进 译 译更多章节内容可以访问云栖社区“华章计算机”公众号查看。

2.3.4 上下界

在本书中,我们简化了“大O”表示法,目的是对不同问题样本在持续增长的规模n下算法性能进行分类。这种分类使用O(f(n))表示,其中f(n)是一些如n、n3或者2n的常见函数。
例如,假设存在一个算法,当输入数据规模“足够大”时,它在最坏情况下的性能绝不大于和输入问题样本规模成比例的某个值。更加精确地说,对于所有的n > n0,存在某个常数c > 0,满足t(n) ≤ cn ,其中n0是每个问题样本“足够大时”的基本点。在这种情况下,分类函数f(n) = n,采用O(n)进行表示。如果对于同样的算法,假定它在最好情况下的性能绝不小于和输入问题的样本规模成比例的某个值,即对于所有的n > n0,存在不同的常数c和问题规模临界值n0,满足t(n) ≥ cn。那么在这种情况下的分类依然是f(n) = n,但是会采用Ω(n)进行表示。
正式符号的总结如下:
算法执行时间的下界记作Ω(f(n)),对应于最好情况。
算法执行时间的上界记作O(f(n)),对应于最坏情况。
考虑上述两种情况是有必要的。细心的读者会指出,使用函数f(n) = c*2n也可以将上述算法归类为O(2n),尽管这种方式描述了一种更慢的行为。这么描述虽然没错,但是提供的信息量太少,就好比说,你需要花上不多于一个星期的时间完成一个只需要5min就能完成的任务。在本书中,我们总是使用最接近的匹配表示算法分类。
在复杂性理论中,还有一种Θ(f(n))表示,它融合了上下界的思想,用于描述精确的紧界(tight bound),即下界为Ω(f(n))时,上界则是使用相同分类函数f(n)的O(f(n))。我们采用更为广泛接受的(更加非正式一些的)O(f(n))来简化算法表示和分析。我们保证,在讨论算法性能时,如果一个算法被认定为O(f(n)),一定不会存在更为精确的f'(n)可以对算法进行分类。

相关文章
|
5天前
|
SQL 存储 算法
【MySQL技术内幕】6.4-锁的算法
【MySQL技术内幕】6.4-锁的算法
21 1
|
5天前
|
存储 算法 关系型数据库
【MySQL技术内幕】5.7- InnoDB存储引擎中的哈希算法
【MySQL技术内幕】5.7- InnoDB存储引擎中的哈希算法
12 1
|
7天前
|
算法 C语言 Ruby
分形逃逸时间算法中的 Normalized Iteration Count(NIC)技术 让颜色更柔和
Normalized Iteration Count (NIC) 技术是一种提升逃逸时间算法中分形图像质量的方法,它产生更平滑的颜色过渡。数学公式表示为:`mu = n + 1 - log(log(|Z(n)|)) / log(p)`,其中 `Z(n)` 是迭代次数,`|Z(n)|` 是复数模长,`p` 通常取2。示例代码提供了 Ruby, Maxima 和 C 语言的实现。
|
9天前
|
存储 自然语言处理 算法
编辑距离算法全解析:优化文本处理的关键技术
编辑距离算法全解析:优化文本处理的关键技术
|
12天前
|
存储 运维 算法
社交软件红包技术解密(十三):微信团队首次揭秘微信红包算法,为何你抢到的是0.01元
本文中,我们将介绍几种主流的IM红包分配算法,相信聪明的你一定能从中窥见微信红包技术实现的一些奥秘。
13 0
|
14天前
|
算法 NoSQL Python
开山之作!Python数据与算法分析手册,登顶GitHub!
若把编写代码比作行军打仗,那么要想称霸沙场,不能仅靠手中的利刃,还需深谙兵法。 Python是一把利刃,数据结构与算法则是兵法。只有熟读兵法,才能使利刃所向披靡。只有洞彻数据结构与算法,才能真正精通Python。
|
15天前
|
存储 人工智能 算法
RAG技术的高级应用和算法
文章主要探讨了RAG技术的高级应用和算法,系统化地整理了各种方法。
|
15天前
|
机器学习/深度学习 数据采集 算法
基于机器学习的推荐算法构建技术详解
【6月更文挑战第4天】本文详述了构建基于机器学习的推荐算法,特别是协同过滤方法。从用户和物品相似性的角度,解释了用户-用户和物品-物品协同过滤的工作原理。涵盖了数据准备、预处理、特征工程、模型训练、评估优化及结果展示的构建流程。推荐算法在电商、视频和音乐平台广泛应用,未来将受益于大数据和AI技术的进步,提供更智能的推荐服务。
|
20天前
|
算法 NoSQL Python
开山之作!Python数据与算法分析手册,登顶GitHub!
若把编写代码比作行军打仗,那么要想称霸沙场,不能仅靠手中的利刃,还需深谙兵法。 Python是一把利刃,数据结构与算法则是兵法。只有熟读兵法,才能使利刃所向披靡。只有洞彻数据结构与算法,才能真正精通Python
|
28天前
|
存储 算法 搜索推荐
【大数据分析与挖掘技术】Mahout推荐算法
【大数据分析与挖掘技术】Mahout推荐算法
23 0

热门文章

最新文章