当前位置:首页 » 操作系统 » 算法好坏三条

算法好坏三条

发布时间: 2023-07-17 11:10:19

Ⅰ 如何比较两个算法的好坏,有什么指标

算法是一个良定义的计算过程,以一个或多个值输入,并以一个或多个值输出。
评价算法的好坏的因素:·算法是正确的;
·执行算法的时间;
·执行算法的存储空间(主要是辅助存储空间);
·算法易于理解、编码、调试。
**************************************************************************************************************
时间复杂度:是某个算法的时间耗费,它是该算法所求解问题规模n的函数。
渐近时间复杂度:是指当问题规模趋向无穷大时,该算法时间复杂度的数量级。
评价一个算法的时间性能时,主要标准就是算法的渐近时间复杂度。
算法中语句的频度不仅与问题规模有关,还与输入实例中各元素的取值相关。
时间复杂度按数量级递增排列依次为:常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n^2)、立方阶O(n^3)、……k次方阶O(n^k)、指数阶O(2^n)。
空间复杂度:是某个算法的空间耗费,它是该算法所求解问题规模n的函数。
算法的时间复杂度和空间复杂度合称算法复杂度。

Ⅱ 评价一个算法性能好坏的重要标准是

1、时间复杂度

算法的时间复杂度是指执行算法所需要的计算工作量。一般来说,计算机算法是问题规模n 的函数f(n),算法的时间复杂度也因此记做宽咐。

3、正确性

算法的正滚旦确性是评价一个算法优劣的最重要的标准。

4、可读性

算法的可读性是指一个算法可供人们阅读的容易程度。

5、健壮性

健壮性是指一个算法对不合理数据输大巧扰入的反应能力和处理能力,也称为容错性。

Ⅲ 如何评价一个算法的好坏

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

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!)称为指数时间。

Ⅳ 算法分析:如何分析一个算法的效率好坏

当我们说算法分析的时候我们在说什么?(狭义的技术层面的定义):
算法分析指的是: 对算法在运行时间和存储空间这两种资源的利用效率进行研究
即时间效率和空间效率。

时间效率指算法运行有多快;
空间效率指算法运行时需要多少额外的存储空间。
(时间效率也叫时间复杂度;空间效率也叫空间复杂度。)

在计算机时代早期,时间和空间这两种资源都是及其昂贵的。但经过半个多世纪的发展,计算机的速度和存储容量都已经提升了好几个数量级。
现在空间效率已经不是我们关注的重点了,但时间效率的重要性并没有减弱到这种可以忽略的程度。

所以,当我们分析一个算法的的时候,我们只关注它的时间效率

当我们遇到一个算法时,我们可以用这样一个通用的思路去分析它:

首先第一卜伍知步考虑这个算法的输入规模是什么?即输入参数,再换句话说也就是待解决的问题有多大?
从这里入手是因为一个显而易见的规律就是,不管使用什么算法, 输入规模越大,运行效率肯定会更长
输入规模的确定要根据具体要解决的实际问题的细节来决定,相同的问题不同的细节,输入规模是不一样的。比如:一个拼写检查的算法,
如果算法关注的是单独的字符检查,那么字符的数量就是输入规模的大小;
如果算法关注的是词组搭配的检查,那么这个输入规模就要比单独的字符检查的输入规模要小,这里输入规模就是词的数量了。

接下来第二步考虑这个算法的运行时间,即这个算法运行地快慢。
我们可以简单地用计时的方法,即某个算法运行了多少毫秒。
但这个方式有一个缺陷就是在不同计算机上,相同算法的运行时间是不一样,因为有的电脑快有的电脑慢。
所以有没有一种度量方法可以排除这些无关因素?
答案是肯定的,我们可以关注算法执行了多少步,即 操作的运行次数 。而且为了简化问题我们只需关注最重要的操作步骤,即所谓的 基本操作 ,因为基本操作已经足够可以决定这个算法的品质。
比如一个算法通常是最内层的循环中是最费时的操作,那我们就只需要把它循环了多少次作为基本操作进行研究。

这里需要延伸的一点是在大规模的输入情况下考虑执行次数的增长次数。因为针对小规模的输入,在运行时间的差别上不太明显。比如只对100个数字进行排序,不管你用什么排序算法,时间效率都差不多。只有在输入规模变大的时候,算法的差异才变得既明显又重要了起来。
简单来说,
如果一个算法在输入规模变大时,但运行时间平缓增长,那么我们就可以说它就是一个效率高的算法;
而如果一个算法在输入规模变大时,它的运行时间成指数级增长,那就可以说这个算法的效率很差。
总而言之就是,对基本操作的大规模输入情况下的变化的研究才更具有深远意义。

当我们了解了输入规模对算法时间效率的会产生影响,但算法的执行效率却不仅仅只受输入规模的影响,某些情况下,算法的执行效率更取决于输入参数的细节。
比如:一个简单的顺序查找的算法,在数组里查找数字 9:
在数组 l1 = [1, 2, 3, 4, 5, 6, 7, 8, 9 ] 里查找数字 9 和在相同的输入规模的另一个数组 l2 = [ 9 , 1, 2, 3, 4, 5, 6, 7, 8]里查找数字 9,在数组 l2 的执行效率肯定更高。
上面小例子中的两个数组就体现了两个极端: 输入最优情况 输入最坏情况
相对应的,
在输入最优情况下的算法就叫 最优效率
在输入最坏情况下的算法就叫 最差效率
在这里有两个经验性的规则:

在现实情况下,输入是“随机”的,既不会是最优输入也不会是最坏输入。所以这里又型消要引出一个概念,即: 平均效率
首先指出,我们绝不能用“最优效率”和“最差效率”的平均数求得 平均效率 ,即便有时间这个平均数和真正的 平均效率 巧合地一致。
正确的步骤是:我们要对输入规模 n 做一些假设。
对于上面的顺序查找算法的例子,标准的假设有两个:

基于这两个假设求平均效率可得:

由此,平均效率橘燃 C(n) = p(n+1) / 2 + n(1-p)

由此可知,

从这个例子可以发现,平均效率的研究要比最差效率和最优效率的研究困难很多:
我们要将输入规模 n 划分为几种类型,对于同类型的输入,使得算法的执行次数是相同的。

算法是计算机科学的基础,以后会继续更新算法相关的随笔,对算法感兴趣的朋友欢迎关注本博客,也欢迎大家留言讨论。
我们正处于大数据时代,对数据处理感兴趣的朋友欢迎查看另一个系列随笔:
利用Python进行数据分析 基础系列随笔汇总

Introction to The Design and Analysis of Algorithms, Third Edition by Anany Leitin

Ⅳ 如何判断算法优劣

算法的好坏是看它的运行效率比如递归一般来说是比较耗时间的,也就是说效率低当然也看具体情况,有的算法在基数小的情况是差不多,性能反而还好点

Ⅵ 衡量算法好坏的标准

1:时间复杂度:

可以简单的说就是:大概程序要被执行的次数,而非时间。注意:是次数,不是时间,因为不同机器的性能是不一样的,不要用计时器在那里计时谁的更快。当然,如果在同一台电脑上运行计时另说。
Question:怎样看待一个程序执行的速度是快还是慢?
Answer:要看他里边最关键的运行次数最多的那一个步骤到底执行了几次,用这个来衡量算法的时间复杂度

2:空间复杂度:

同样简单来说就是:算法执行过程中大概所占用的最大的内存。

3:难易程度:

所研究的算法尽可能让大家能看懂。

4:健壮性:

简单来说哦,不要一碰就完不结实

5:正确性:

一定要正确,感觉这一特性说不说都是可以,不正确也不能用,这一切的前提都是以正确为前提的。

热点内容
分部数据库服务器的IP地址有效 发布:2025-03-16 06:33:40 浏览:191
安卓项目如何配置tomacat 发布:2025-03-16 06:31:13 浏览:430
写脚本测试 发布:2025-03-16 06:20:07 浏览:779
多个拨号宽带如何配置 发布:2025-03-16 05:51:35 浏览:687
管理员c语言 发布:2025-03-16 05:40:17 浏览:341
安卓软件上的图案如何更改 发布:2025-03-16 05:35:57 浏览:747
2010编译c中文乱码 发布:2025-03-16 05:33:40 浏览:549
干一杯密码箱酒多少钱一箱 发布:2025-03-16 05:31:15 浏览:357
我的零钱通密码是多少 发布:2025-03-16 05:04:36 浏览:937
编程猫酷跑 发布:2025-03-16 04:58:35 浏览:321