《算法技术手册》一2.1 问题样本的规模

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

2.1 问题样本的规模

问题样本是解决问题的程序所使用的特定输入数据集。在大部分问题中,随着这一数据集规模的增长,程序的执行时间也在不断增加。同时,过度地对样本数据进行编码(可能使用了压缩技术),可能会不必要地降低程序的执行效率。寻找一种最优的样本编码方式是极其困难的,因为问题发生在复杂的现实世界,而且还需要进行合理的翻译才能被程序求解。
在评估算法时,我们会尽量假定问题样本的编码并不是影响算法效率的决定性因素。问题样本的表现方式应当仅仅依赖于待执行操作的类型。设计高效的算法通常从选择一个合适的数据结构开始。
由于没法对问题样本给出正式定义,因此我们假设样本以一种简洁且可以普遍接受的方式对样本进行编码。例如,当对n个数字进行排序时,根据惯例,我们会假定数字可以存储在计算平台上32位的字长里,并且待排序的样本规模为n。假如某些数字需要用多于1个字长的空间存储,例如某个固定数量的字长,那么在衡量样本空间时会多乘上一个常量。
算法研究人员认为,即使给定编码方式,要精确计算出性能费用也是不切实际的。因此,他们断言,如果一些算法的性能费用仅仅是常数倍的差异,那么它们可以被认为是渐近等价的。换句话说,问题空间的不断增长所带来的算法性能差异是无关紧要的。举例来说,处理64位整数要比处理32位整数需要更长的处理时间,但是这些差异是可以忽略不计的。如果一个优秀的算法能够处理上百万的32位整数,那么它同样可以处理相同数量的64位整数。不过,这个假定在现实世界中是不可行的(谁会愿意将自己应付的账单乘上1000 呢?),因此这种方式只作为算法比较时的一种通用手段。
对于本书所涉及的算法,常量对所有平台的影响几乎都是很小的,但在产品代码中具体实现算法时,读者还必须要注意这些常数所带来的影响。这种渐近表示方式之所以非常实用,是因为它可以根据算法在小数据中的性能,来预测其在大数据中的性能。此外,它可以帮助决定特定算法实现能够处理的最大问题样本(Bentley,1999)。
大多数编程语言都支持使用数组存储数据集。数组是一块连续的内存区域,这些区域可以通过整数索引i直接和快速地存取第i个元素。当数组元素大小都在1个字长以内时,可以使用一维数组存储(例如整数数组和布尔数组)。当然,数组还可以扩展到多维来表示更为复杂的数据。

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

热门文章

最新文章