0°

算法基本概念

内容预览:
  • 始发于微信公众号: 程序员小乐 分享编程技能、互联网技术、生活感悟、...~
  • 2. 如何评价算法 为了实现同样一个需求,可以设计出各种不同的算法~
  • 一般来说,知道这些就够了~

始发于微信公众号: 程序员小乐

分享编程技能、互联网技术、生活感悟、打造干货分享平台,将总结的技术、心得、经验分享给大家,这里不只限于技术!还有职场心得、生活感悟、以及面经点击上方 “杨守乐” ,选择“置顶公众号”,第一时间送达!



1. 算法是什么

算法:顾名思义,一种计算的方法,在程序设计上,就表现为一组指令序列。

为了使得算法有意义,还规定算法必须是有限的和确定的,也就是说算法的执行时间有限、执行的过程是确定的。

比如我们写了代码

int a = 10;               //a,b为输入数据  
int b = 20;  
int c = a+b;     //c为输出数据,算法为加法运算  

这其实就是一个算法的具体实现(程序就是算法的具体实现,但不是所有程序都能认为是算法的实现,比如while(1) 死循环程序,因为不满足算法的有限性)。

总结:

算法具有4个性质:输入、输出、确定性、有限性
算法是方法,程序是方法的具体实现
当一个算法对每组输入数据,都能得到正确的输出数据,则称算法是正确的,否则称之为错误的。

2. 如何评价算法

为了实现同样一个需求,可以设计出各种不同的算法。

典型的,对一组数据排序,可以有直接插入法、冒泡排序法、堆排序等等;

简单的,实现从1累加到100,可以计算1+2+…+100,也可以计算50*(1+100);

3. 如何评价一个算法的优劣?

对于程序设计而言,无非就是两个方面:
算法有多快?(时间效率);
内存耗得多不多?(空间效率)

我们称之为算法的复杂度分析,包括上述两个方面,各自称为时间复杂度分析和空间复杂度分析。通常我们更关注的是算法的时间复杂度。

4. 时间复杂度分析

设问题规模为n,即输入数据的大小,时间复杂度记为T(n)

比如n个输入数据,需要做2n个基本运算,那么T(n) = 2n

下面的程序中,对一个n数据遍历了两次,其T(n) = 2*n

#include <stdio.h>  
#define n 5  
int main()  
{        
        int i;  
        int data[n] = {1,2,3,4,5};  
        for(i=0;i<n;i++)  
        {  
                data[i] += 1;  
        }  
        for(i=0;i<n;++)  
        {  
                printf("%d",data[i]);  
        }  
        return 0;  
}  

再如嵌套两次循环,每次循环都是1至n,则其T(n) = n2

这里提的基本运算,可以是一条语句,也可以是一组语句,更具实际情况而定。

渐进时间复杂度

通常,我们分析算法的复杂度不需要考虑的这么具体,精确到2n,3n2+1等等,只需要考虑它的数量级就可以了,这就是渐进时间复杂度O(n),也即是nà∞时,T(n) -> O(n)

备注:准确的说,O(n) 是渐进上界,相对的也就有渐进下界。但在实际分析时,通常直接说某某算法的时间复杂度为O(n)

O(n) 其实就是T(n)省略了低阶项和常数项

比如:

T(n) = 2*n        则O(n)=n,     实际中就称算法时间复杂度为n

T(n)= 3*n2           则O(n)=n2,  实际中就称算法时间复杂度为n2

T(n) =3* log(n)则O(n)=log(n),    实际中就称算法时间复杂度为log(n)

空间复杂度分析

分析算法运行过程中所占用存储空间大小,其分析和时间复杂度类似。

如果使用1个基本空间单位,则空间复杂度为O(1)

如果使用n个基本空间单位,则空间复杂度为O(n)

这里说的空间复杂度实际中也是渐进空间复杂度。

以上就是结合实际使用,给出的算法的基本概念。一般来说,知道这些就够了。

如果有兴趣了解更多,可以自己查找更专业的资料来补充。

如果您觉得不错,请别忘了转发、分享、点赞让更多的人去学习, 您的举手之劳,就是对小乐最好的支持,非常感谢!

如何您想进技术群和大牛们交流,关注公众号在后台回复 “加群”,或者 “学习” 即可

来自:jarvischu

链接:

http://blog.csdn.net/jarvischu/article/details/13829287

著作权归作者所有。本文已获得授权。欢迎投稿。

每日英文


A person, if you don’t force yourself, you don’t know how good.

一个人,如果你不逼自己一把,你根本不知道自己有多优秀。

乐乐有话说

人通过不断努力而拥有的东西,一旦成为负累,无论多么好,都不在使人快乐。放弃他们的过程就是重新找回自我的过程,太多的人想要找回自我,然而如果代价是让你放弃之前几十年努力得来的东西,他们最终还是会选择在没有自我的日子里混日子。

算法基本概念


推荐阅读






看完本文有收获?请转发分享给更多人
关注「杨守乐」,提升技能

以上就是:算法基本概念 的全部内容。

本站部分内容来源于互联网和用户投稿,如有侵权请联系我们删除,谢谢。
Email:[email protected]


0 条回复 A 作者 M 管理员
    所有的伟大,都源于一个勇敢的开始!
欢迎您,新朋友,感谢参与互动!欢迎您 {{author}},您在本站有{{commentsCount}}条评论