影响算法效率的因素
1、从大的方面来讲,所选择的语言对算法的效率影响很大。一般来说,使用越高级的语言所需要的时间和空间就越大。另外,不同编译器产生的代码质量不同,这对算法的效率也会有影响。
2、存储结构
数据的存储结构,分为顺序存储结构和链式存储结构。顺序存储结构的特点是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系;链式存储结构则是借助指示元素存储地址的指针表示数据元素之间的逻辑关系。不同的问题求解选用不同的存储结构。
例:稀疏矩阵的存储和转置算法
(1)存储
如果采用数组的方式进行存储,对稀疏矩阵来说有很多零元素,因而浪费空间严重,因此我们对稀疏矩阵进行压缩存储。只存储稀疏矩阵的非零元素。在数据结构教材中用三元组表示方法,建立三元组顺序表。
//..................................................................................................................
#define MAXSIZE 12500
typedef struct{
int i,j;
ElemType e;
}Triple;
Typedef struct{
Triple data[MAXSIZE + 1];
int mu,nu,tu;
}TSMatrix;
//....................................................................................
(2)转置
直接进行转置时,对要转置的A表从第一行起扫描一遍,按照原矩阵的列序进行转置,得到的新矩阵是以行序为主序的。但是这样做只适合于非零元素的个数非常少的情况,否则和矩阵的直接转置算法时间复杂度相差无几。
改进:矩阵的快速转置算法
附设两个变量,num[col]表示矩阵中第col 列中非零元的个数,cpot[col]表示第col 列第一个非零元在b.data中的位置。
我们可以再矩阵转置之前将我们附设的两个变量都求出来,然后进行转置,即为快速转置算法。
3、指针操作
在使用指针时,指针的有秩序扫描非常重要。例如在模式匹配中,如果直接进行匹配,当有不完全匹配时,主串的指针需要回溯。在KMP算法中,我们先可以求出每个元素的next函数值,从而在发生不完全匹配时,主串的指针不必要回溯,只需要模式串的元素回到当前元素的next函数值所指的元素再进行匹配即可。当主串和模式串有很多不完全匹配时,KMP算法可以大大提高效率。
4、查找的效率
有很多快速查找的算法都可以提高查找的效率,如建立索引,折半查找等,都是在记录和关键字之间进行比较,从而寻求关系。这一类查找建立在比较的基础之上。查找的效率依赖于查找过程中所进行的比较次数。
哈希表
在哈希表中,使得记录的存储位置和关键字之间建立一个确定的存储关系,因而在查找时,只需要根据这个对应的关系f 找到给定值K 的像f(k)。用这个思想建立哈希表。如在基因组匹配时,用哈希表非常方便。
5.数据类型的选择
数据类型的选择也会影响算法效率,在对时间和空间要求非常严格时,尽可能的使用占用空间较小的数据类型。使用动态开辟空间会使得效率降低,所有在能确定或估计出需要的空间大小的情况下尽量使用静态数字。个人觉得用vector虽然方便,但是效率并不高。
6、存储方式
用堆操作还是用栈操作,对于不同的问题需要仔细选择。在串和队列的有关操作中用堆操作合适,在树的操作中用栈操作合适,如建立二叉树中序遍历的递归算法或非递归算法,用栈操作好。
数据分析咨询请扫描二维码
统计学基础 - 理解统计学的基本概念和方法是数据分析师必备的技能之一。统计学为他们提供了处理数据、进行推断和建模的基础。 数 ...
2024-11-25数据分析师在如今信息爆炸的时代扮演着至关重要的角色。他们不仅需要具备扎实的数据分析技能,还需要不断学习和适应不断发展的技 ...
2024-11-25数据分析师的工作职责涉及多个关键方面,从数据的获取到处理、分析再到可视化,旨在为企业的决策提供有力支持。让我们深入了解数 ...
2024-11-25数据分析师:洞察力量的引擎 数据分析师的兴起 数据分析师行业目前正处于快速发展阶段,市场需求持续增长,薪资水平也有所提升。 ...
2024-11-25数据收集与整理 - 从各种来源收集数据,清洗和整理以确保数据质量和可用性。 数据分析与建模 - 运用统计学方法和机器学习模型对 ...
2024-11-25数据分析是当今社会中不可或缺的一项技能,涵盖了广泛的工具和技术。其中,掌握各种数据处理函数对于数据分析师至关重要。本文将 ...
2024-11-25“大数据治理”是一个涵盖广泛的复杂概念,其核心在于确保大规模、多样化的数据资源能够被有效管理和利用。不仅涉及数据的采集、 ...
2024-11-25一、引言 背景介绍 随着信息技术的快速发展和互联网的普及,大数据已经成为现代社会的重要资产。大数据的兴起不仅推动了各行各业 ...
2024-11-25《Python数据分析极简入门》 第2节 7 Pandas分组聚合 分组聚合(group by)顾名思义就是分2步: 先分组:根据某列数据的值进行 ...
2024-11-25数据分析需要学习的内容非常广泛,涵盖了从理论知识到实际技能的多个方面。以下是数据分析所需学习的主要内容: 数学和统计学 ...
2024-11-24数据分析师需要具备一系列多方面的技能和能力,以应对复杂的数据分析任务和业务需求。以下是数据分析师所需的主要能力: 统计 ...
2024-11-24数据分析师需要学习的课程内容非常广泛,涵盖了从基础理论到实际应用的多个方面。以下是根据我搜索到的资料整理出的数据分析师需 ...
2024-11-24《Python数据分析极简入门》 第2节 6 Pandas合并连接 在pandas中,有多种方法可以合并和拼接数据。常见的方法包括append()、conc ...
2024-11-24《Python数据分析极简入门》 第2节 5 Pandas数学计算 importpandasaspdd=np.array([[81,&n ...
2024-11-23数据分析涉及多个方面的学习,包括理论知识和实践技能。以下是数据分析需要学习的主要方面: 基础知识: 数据分析的基本概念 ...
2024-11-22数据分析适合在多个单位工作,包括但不限于以下领域: 金融行业:金融行业对数据分析人才的需求非常大,数据分析师可以从事经 ...
2024-11-22数据分析是一种涉及从大量数据中提取有用信息和洞察力的过程。其工作内容主要包括以下几个方面: 数据收集与整理:数据分析师 ...
2024-11-22数据分析师需要掌握多种技能,以确保能够有效地处理和分析数据,并为业务决策提供支持。以下是数据分析师需要掌握的主要技能: ...
2024-11-22数据开发和数据分析是两个密切相关但又有所区别的领域。以下是它们的主要区别: 定义和目标: 数据开发:数据开发涉及数据的 ...
2024-11-22数据架构师是负责设计和管理企业数据架构的关键角色,其职责涵盖了多个方面,包括数据治理、数据模型设计、数据仓库构建、数据安 ...
2024-11-22