当前位置:首页 » 操作系统 » 算法怎么样

算法怎么样

发布时间: 2023-08-01 16:17:42

‘壹’ 计算机算法设计与分析怎么样

这本书作为这个学期的算法课教材,这才让我有机会看了下此书,刚看的时候,云里来雾里去的,看完后,更是无奈。不明白为什么这样的书会作为教材,毫无道理。原因如下: 1.书中所讲内容大部分出自算法导论和Levitin的算法设计与分析基础(见P86页讲贪心算法用做举例的找零问题中的二角五分硬币,当时看到二角五分硬币就瞬间无语了.....因为只有米国才有25分的硬币 = =),有些地方让人感觉是删减后照搬过来的,因此读起来特别费劲,自觉愚钝,跟不上作者跳跃的思维。 2.讲的东西难度适中,当是表达方式实际上给读者增加了难度。书中经常用a[],b[]这样的名字来命名所需的数据结构,可见作者丝毫没有用心在写书,根本不为读者着想,无力形式化描述使读起此书颇有难度。 3.最关键的在于书中的算法代码。没有采用伪代码而采用c++实现本身没什么问题,但是代码的风格实在是不敢恭维。从变量命名上多采用s,k,r之类让人无语的名字,根本无法清晰表达变量的意思,而且要命的大部分算法只有很少的注释或者根本没有,注释固然不能太多,但那也是建立在代码能自文档化的基础上的,面对这样的代码,只能摇头。除此之外,书中代码还出现风格不统一的情况,关于花括号的使用,一会是K&R风格,一会是悬挂式风格,有时干脆两种风格混在同一段代码中,及其容易误导他人,使其养成不良的代码风格。 综上,要是学算法的话,这本书并不是很理想,我觉得Levitin的那本算法设计与分析基础不错,而这本只能算不是教材的教材吧.

‘贰’ hash算法是怎么样的

hash算法是一种散列算法,是把任意的长度的输入,转换成固定的额输出,福鼎的输出,输出的是散列值。在空间的比较中,输入的空间是远大于输出的散列值的空间,不同输入散列成同样的输出,一般很难从输出的散列值获取输入值的。

常用的hash函数有直接取余法、乘法取整法,平方取中法。在直接取余法中,质数用到的比较多,在乘法取整法中,主要用于实数,在平方取中法里面,平方后取中间的,每位包含的信息比较多些。

Hash在管理数据结构中的应用

在用到hash进行管理的数据结构中,就对速度比较重视,对抗碰撞不太看中,只要保证hash均匀分布就可以。比如hashmap,hash值(key)存在的目的是加速键值对的查找,key的作用是为了将元素适当地放在各个桶里,对于抗碰撞的要求没有那么高。

换句话说,hash出来的key,只要保证value大致均匀的放在不同的桶里就可以了。但整个算法的set性能,直接与hash值产生的速度有关,所以这时候的hash值的产生速度就尤为重要。

‘叁’ 如何评价一个算法的好坏

首先,这个算法必须是正确的
其次,好的算法应该是友好的,便于人们理解和交流,并且是机器可执行的。
这个算法还需要足够健壮,即当输入的数据非法或不合理时,也能适当的做出正确的反应或进行相应的处理
最后它还必须拥有高效率和低存储量要求。
也就是所谓的时间复杂度和空间复杂度

1.时间复杂度

定义:在计算机科学中,算法的时间复杂度是一个函数,他定量描述了该算法的运行时间.一个算法执行所耗费的时间,从理论上讲,只有你把你的程序放机器上跑起来,才能知道.然而我们有一套时间复杂度的分析方式.一个算法所花费的时间与其中语句的执行次数成正比例.算法中的基本操作的执行次数,为算法的时间复杂度.

2.时间复杂度为什么不使用时间来衡量而使用基本语句的运行次数来衡量?

算法的执行时间依赖于具体的软硬件环境,所以,不能用执行时间的长短来衡量算法的时间复杂度,而要通过基本语句执行次数的数量级来衡量。

3.时间复杂度的O渐进表示法(Big O notation)

是用于描述函数渐进行为的数学符号.

大O阶方法推导:
计算基本语句的执行次数的数量级;
只需计算基本语句执行次数的数量级,这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可,可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析,并且使注意力集中在最重要的一点上:增长率。
如果算法中包含嵌套的循环,则基本语句通常是最内层的循环体,如果算法中包含并列的循环,则将并列循环的时间复杂度相加。例如:

for (i=1; i<=n; i++)
x++;
for (i=1; i<=n; i++)
for (j=1; j<=n; j++)
x++;

第一个for循环的时间复杂度为Ο(n),第二个for循环的时间复杂度为Ο(n2),则整个算法的时间复杂度为Ο(n+n2)=Ο(n2)。

4.时间复杂度的:最优、平均、最差情况,为什么时间复杂度看的是最差情况?

最差情况下的复杂度是所有可能的输入数据所消耗的最大资源,如果最差情况下的复杂度符合我们的要求,我们就可以保证所有的情况下都不会有问题。

某些算法经常遇到最差情况。比如一个查找算法,经常需要查找一个不存在的值。
也许你觉得平均情况下的复杂度更吸引你,可是平均情况也有几点问题。第一,难计算,多数算法的最差情况下的复杂度要比平均情况下的容易计算的多,第二,有很多算法的平均情况和最差情况的复杂度是一样的. 第三,什么才是真正的平均情况?如果你假设所有可能的输入数据出现的概率是一样的话,也是不合理的。其实多数情况是不一样的。而且输入数据的分布函数很可能是你没法知道。
考虑最好情况的复杂度更是没有意义。

5.如何求解:二分查找、递归求阶乘、递归斐波那契的时间复杂度?

二分查找:通过折纸查找求解时间复杂度为O(logN);
递归求阶乘:数基本操作递归N次得到时间复杂度为O(N);
递归斐波那契:分析得出基本操作递归了2N次,时间复杂度为O(2N);

6.什么是空间复杂度?

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的度量.空间复杂度不是程序占用了多少bytes的空间,因为这个也没太大意义,所以空间复杂度算的是变量的个数.空间复杂度计算规则基本跟时间复杂度类似,也使用大O渐进法表示.

7.如何求空间复杂度? 普通函数&递归函数

一个算法的空间复杂度只考虑在运行过程中为局部变量分配的存储空间的大小,它包括为参数表中形参变量分配的存储空间和为在函数体中定义的局部变量分配的存储空间两个部分。若一个算法为 递归算法,其空间复杂度为递归所使用的堆栈空间的大小,它等于一次调用所分配的临时存储空间的大小乘以被调用的次数(即为递归调用的次数加1,这个1表示开始进行的一次非递归调用)。算法的空间复杂度一般也以数量级的形式给出。如当一个算法的空间复杂度为一个常量,即不随被处理数据量n的大小而改变时,可表示为O(1);当一个算法的空间复杂度与以2为底的n的对数成正比时,可表示为O(log2n);当一个算法的空间复杂度与n成线性比例关系时,可表示为O(n).若形参为数组,则只需要为它分配一个存储由实参传送来的一个地址指针的空间,即一个机器字长空间;若形参为引用方式,则也只需要为其分配存储一个地址的空间,用它来存储对应实参变量的地址,以便由系统自动引用实参变量。
8. 分析递归斐波那契数列的:时间、空间复杂度,并对其进行优化,伪递归优化->循环优化

long long Fib(int N) {
if (N < 3)
return 1;
return Fib(N - 1) + Fib(N - 2);
}

普通递归实现的斐波那契数列:
时间复杂度:O(2^n)

计算并根据O渐进表示法得出时间复杂度.

空间复杂度:O(N);递归深度乘以(每一次递归的空间占用{有辅助空间或常量})

伪递归优化:

long long fib (long long first, longlong second, int N) {
if(N <3)
return 1;
if(N == 3)
return first + second;
return fib(second, first+second,N-1);
}

时间复杂度:
O(N);
递归深度乘以每次递归的循环次数
空间复杂度:
O(1)或O(N)
关键看编译器是否优化,优化则为O(1)否则O(N);

循环优化:

long long Fib(int N) {
long long first = 1;
long long second = 1;
long long ret = 0;
for (int i = 3; i <= N ; ++i) {
ret = first + second;
first = second;
second = ret;
}
return second;
}

时间复杂度:O(N);

空间复杂度:O(1);

9.常见时间复杂度

常见的算法时间复杂度由小到大依次为: Ο(1)<Ο(log2n)<Ο(n)<Ο(nlog2n)<Ο(n2)<Ο(n3)<…<Ο(2n)<Ο(n!) Ο(1)表示基本语句的执行次数是一个常数,一般来说,只要算法中不存在循环语句,其时间复杂度就是Ο(1)。Ο(log2n)、Ο(n)、Ο(nlog2n)、Ο(n2)和Ο(n3)称为多项式时间,而Ο(2n)和Ο(n!)称为指数时间。

‘肆’ 如何衡量一个算法的优劣有哪些标准

如何衡量一个算法的优劣,见人见智。一个好的算法首先是要能够满足场景的需求,其次是在能够最大限度的节省资源(最低成本原则),最后是实现逻辑简单,比较容易理解(本质上也是最低成本原则)。但是,在现实中硬件资源不变,算法不变情况下,算法执行的效率提高,相对应往往是资源消耗增加。一个合格的算法是在一个可以接受的范围内满足场景需求,而一个优秀的算法则是在满足场景需求的基础上,最大限度的节省资源,简化逻辑。

比如我要完成一项计算任务,要求是在5分钟执行完成。现在有算法1:需要执行1分钟,消耗内存8G;算法2需要执行3分钟,需要消耗内存256M。那么,我们应该如何选择呢?首先,这两种方案都能满足我们的需求;其次:算法1的需要消耗的资源是算法2的32倍,算法1的效率是算法2的3倍。在这种满足需求的情况下,往往更倾向于选择算法2。衡量一个算法的优劣往往要评估多方因素,结合实践,综合比较最终得出结论。

衡量一个算法的的标准主要有3个: 算法的执行效率 算法的内存消耗 算法的稳定性

‘伍’ 算法的特性是怎么样的

算法的基本特性

1、有穷性

算法的有穷性是指算法必须能在执行有限个步骤之后终止;

2、确切性

算法的每一步骤必须有确切的定义;

3、输入项

一个算法有0个或多个输入,以刻画运算对象的初始情况,所谓0个输入是指算法本身定出了初始条件;

4、输出项

一个算法有一个或多个输出,以反映对输入数据加工后的结果。没有输出的算法是毫无意义的。


算法分类

一、有限的,确定性算法这类算法在有限的一段时间内终止。他们可能要花很长时间来执行指定的任务,但仍将在一定的时间内终止。这类算法得出的结果常取决于输入值。

二、有限的,非确定算法这类算法在有限的时间内终止。然而,对于一个(或一些)给定的数值,算法的结果并不是唯一的或确定的。

三、无限的算法是那些由于没有定义终止定义条件,或定义的条件无法由输入的数据满足而不终止运行的算法。通常,无限算法的产生是由于未能确定的定义终止条件。

‘陆’ 算法工程师的就业前景如何

人工智能工作最受欢迎。算法工程师平均招聘工资建议达到25978元。由于人才匮乏,企业竞争激烈,平均加薪超过7%。该市90%以上的人工智能高薪工作都在天河区.近日,由广州天河人才港和BOSS直接就业研究院联合发布的《广州市天河区2018年1-4月人才趋势报告》,展示了该地区的主流发展趋势:IAB已经成为天河区,和天河区创新型企业和大型企业布局或发展的核心主方向,企业以高薪吸引更多的行业优秀人才。“天河区企业渴望以高薪攫取IAB人才,这意味着企业要在这些行业中发挥实力。

‘柒’ 如何看待计算机算法

计算机算法就是通过一定的步骤求解对应的问题。
因为计算机的资源有限,所以算法需要考虑计算的时间和需要的存储空间,也就是常说的时间复杂度和空间复杂度。
一个算法必须具备以下性质:

(1)算法首先必须是正确的,即对于任意的一组输入,包括合理的输入与不合理的输入,总能得到预期的输出。如果一个算法只是对合理的输入才能得到预期的输出,而在异常情况下却无法预料输出的结果,那么它就不是正确的。

(2)算法必须是由一系列具体步骤组成的,并且每一步都能够被计算机所理解和执行,而不是抽象和模糊的概念。

(3)每个步骤都有确定的执行顺序,即上一步在哪里;下一步是什么,都必须明确,无二义性。

(4)无论算法有多么复杂,都必须在有限步之后结束并终止运行;即算法的步骤必须是有限的。在任何情况下,算法都不能陷入无限循环中。

热点内容
变量的存储分配 发布:2025-03-14 15:01:12 浏览:171
php的初始化 发布:2025-03-14 14:59:20 浏览:598
c语言链表数组 发布:2025-03-14 14:59:08 浏览:101
王者安卓区转苹果区会有什么变化 发布:2025-03-14 14:44:44 浏览:305
思迅收银系统数据服务器ip 发布:2025-03-14 14:44:35 浏览:473
商云x加密狗 发布:2025-03-14 14:44:28 浏览:670
如何快速清除手机图形密码 发布:2025-03-14 14:32:03 浏览:444
电子邮件账户的服务器该怎么填写 发布:2025-03-14 14:31:59 浏览:421
泰拉瑞亚蒲公英怎么开在线服务器 发布:2025-03-14 14:21:20 浏览:629
如何破坏门上的密码锁 发布:2025-03-14 14:19:39 浏览:968