《算法技术手册》一2.3.2 平均情况

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

2.3.2 平均情况

考虑设计一个支持n个电话的电话系统,其中n是一个非常大的数——要求在最坏情况下,系统必须能够完成n/2位用户同时呼叫另外n/2位用户。虽然这个系统永远不会由于过载而崩溃,但构造它还是需要花费很高的代价。因为现实生活中,n/2位用户同时呼叫另外n/2位用户发生的概率极小。相反,我们可以设计一个非常容易构建的系统,并借助数学工具来计算由过载导致的系统崩溃的概率。
对于规模为n的样本集合,我们用一个概率分布Pr{si}表示样本分布的概率。其中,单个样本的出现概率为0到1,所有样本的概率的和为1。更加正式一点的定义为,如果Sn是所有规模为n的样本集合,那么:
2017_09_19_155015
如果t()表示算法在单个样本上的执行时间,那么在Sn上的平均执行时间是:
2017_09_19_155126
也就是说,样本si的实际执行时间t(si)会与它作为输入数据的概率加权。如果Pr{si}=0,那么t(si)的实际值将不会影响程序的期望执行时间。我们用Tac(n)表示算法在Sn上的平均执行时间,那么Tac(n)的增长率则表示算法在平均情况下的复杂度。
回忆一下,在描述工作量和时间的增长率时,我们总是会忽略常数,因此顺序搜索n个元素平均情况需要次查找(这符合之前的假设)。按照惯例,在符合这些假设的前提下,顺序搜索需要检查线性数量或者说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技术的进步,提供更智能的推荐服务。
|
4天前
|
算法 JavaScript 决策智能
基于禁忌搜索算法的TSP路径规划matlab仿真
**摘要:** 使用禁忌搜索算法解决旅行商问题(TSP),在MATLAB2022a中实现路径规划,显示优化曲线与路线图。TSP寻找最短城市访问路径,算法通过避免局部最优,利用禁忌列表不断调整顺序。关键步骤包括初始路径选择、邻域搜索、解评估、选择及禁忌列表更新。过程示意图展示搜索效果。
|
4天前
|
机器学习/深度学习 算法
基于BP神经网络和小波变换特征提取的烟草香型分类算法matlab仿真,分为浓香型,清香型和中间香型
```markdown 探索烟草香型分类:使用Matlab2022a中的BP神经网络结合小波变换。小波分析揭示香气成分的局部特征,降低维度,PCA等用于特征选择。BP网络随后处理这些特征,以区分浓香、清香和中间香型。 ```

热门文章

最新文章