影响算法设计的因素有哪些?

如题所述

影响算法设计的有以下因素:

针对机器:空间复杂性和时间复杂性

针对程序员:算法表达和实现的简单性。

针对问题:算法对问题及问题输入规模的普适性。

影响算法效率的因素

1、从大的方面来讲,所选择的语言对算法的效率影响很大。一般来说,使用越高级的语言所需要的时间和空间就越大。另外,不同编译器产生的代码质量不同,这对算法的效率也会有影响。

2、存储结构

数据的存储结构,分为顺序存储结构和链式存储结构。顺序存储结构的特点是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系;链式存储结构则是借助指示元素存储地址的指针表示数据元素之间的逻辑关系。不同的问题求解选用不同的存储结构。

3、指针操作

在使用指针时,指针的有秩序扫描非常重要。例如在模式匹配中,如果直接进行匹配,当有不完全匹配时,主串的指针需要回溯。

在KMP算法中,我们先可以求出每个元素的next函数值,从而在发生不完全匹配时,主串的指针不必要回溯,只需要模式串的元素回到当前元素的next函数值所指的元素再进行匹配即可。当主串和模式串有很多不完全匹配时,KMP算法可以大大提高效率。

4、查找的效率

有很多快速查找的算法都可以提高查找的效率,如建立索引,折半查找等,都是在记录和关键字之间进行比较,从而寻求关系。这一类查找建立在比较的基础之上。查找的效率依赖于查找过程中所进行的比较次数。

哈希表中,使得记录的存储位置和关键字之间建立一个确定的存储关系,因而在查找时,只需要根据这个对应的关系f 找到给定值K 的像f(k)。用这个思想建立哈希表。如在基因组匹配时,用哈希表非常方便。

5、数据类型的选择

数据类型的选择也会影响算法效率,在对时间和空间要求非常严格时,尽可能的使用占用空间较小的数据类型。使用动态开辟空间会使得效率降低,所有在能确定或估计出需要的空间大小的情况下尽量使用静态数字。个人觉得用vector虽然方便,但是效率并不高。

6、存储方式

用堆操作还是用栈操作,对于不同的问题需要仔细选择。在串和队列的有关操作中用堆操作合适,在树的操作中用栈操作合适,如建立二叉树中序遍历的递归算法或非递归算法,用栈操作好。

温馨提示:答案为网友推荐,仅供参考