博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
2.算法
阅读量:5843 次
发布时间:2019-06-18

本文共 1695 字,大约阅读时间需要 5 分钟。

一.算法的概念

算法是特定问题求解步骤的描述

在计算机中表现为指令的有限序列

算法是独立存在的一种解决问题的方法和思想。

对于算法而言,语言并不重要,重要的是思想,也就是说,算法与具体的编程语言无关

二.算法和数据结构的区别

数据结构只是静态的描述了数据元素之间的关系

高效的程序需要在数据结构的基础上设计和选择算法

程序=数据结构+算法 

总结:

算法是为了解决实际问题而设计的

数据结构是算法需要处理的问题载体

数据结构与算法相辅相成

三.算法的特性

输入

  算法具有0个或多个输入

输出

  算法至少有1个或多个输出

有穷性

  算法在有限的步骤之后会自动结束而不会无限循环

确定性

  算法中的每一步都有确定的含义,不会出现二义性

可行性

  算法的每一步都是可行的

四,算法效率的度量-时间复杂度

4.1) 算法效率的度量(大o表示法)

  事前分析估算

  依据统计的方法对算法效率进行估算

4.2) 影响算法效率的主要因素

  算法采用的策略和方法

  问题的输入规模

  编译器所产生的代码

  计算机执行速度

4.3) 大O表示法的原理

大O表示法认为:一个程序转化为指令以后,不管是(加减乘法指令),每一步的运算指令,在一个特定的计算机上,运行时间是一定的。因此只要能够计算出这个程序有多少步,比方说有N步,就可以通过N,来表达出这个程序的复杂度。

算法效率严重依赖于操作(Operation)数量,就是是N的数量

在判断时首先关注操作数量的最高次项

操作数量的估算可以作为时间复杂度的估算

O(5) = O(1)

O(2n + 1) = O(2n) = O(n) 

O(n2+ n + 1) = O(n2)

O(3n3+1) = O(3n3) = O(n3)

4.4) 大O表示法的实际应用

long sum1(int n){    long ret = 0;                                                   1    int* array = (int*)malloc(n * sizeof(int));                     1    int i = 0;                                                      1        for(i=0; i
0 ) { ret = (1 + n) * n / 2;     1 } return ret;}int main(){ printf("%d\n", sum1(100)); printf("%d\n", sum2(100)); printf("%d\n", sum3(100)); return 0;}

如上所示代码,通过对程序运算步数的分析,可以得出:

sum1的时间复杂度:2n+4,记作:O(2n),意思是说这个程序的执行效率是受到n的影响;

sum2的时间复杂度:n+2,记作:O(n)

sum3的时间复杂度:2,记作:O(1),意思是说这个程序能够以常量级执行完毕。

因此从时间复杂度上讲,sum3的算法较优。

 

注意1:判断一个算法的效率时,往往只需要关注操作数量的最高次项,其它次要项和常数项可以忽略。

注意2:在没有特殊说明时,我们所分析的算法的时间复杂度都是指最坏时间复杂度。

五.算法效率的度量-空间复杂度

算法的空间复杂度通过计算算法的存储空间实现

S(n) = O(f(n))

其中,n为问题规模,f(n))为在问题规模为n时所占用存储空间的函数

大O表示法同样适用于算法的空间复杂度

当算法执行时所需要的空间是常数时,空间复杂度为O(1)

 

空间与时间的策略

多数情况下,算法执行时所用的时间更令人关注

如果有必要,可以通过增加空间复杂度来降低时间复杂度

同理,也可以通过增加时间复杂度来降低空间复杂度

 

转载地址:http://mdqcx.baihongyu.com/

你可能感兴趣的文章
php队列使用
查看>>
rabbitMQ
查看>>
struts OGNL表达式
查看>>
【课后服务】20181022切蛋糕
查看>>
JavaScript 语言基础知识点总结(思维导图)
查看>>
第一篇文章
查看>>
Node.js 事件循环
查看>>
Hibernate type 与java 和 数据库类型对应
查看>>
linux nc命令
查看>>
Python对文件的操作(转)
查看>>
Virtualbox安装增强工具失败
查看>>
Caffe cuDNN
查看>>
学习笔记 - MarkDown 语法
查看>>
一个获取a标签传值的函数
查看>>
HR面 - 十大经典提问
查看>>
变动性算法源代码分析与使用示例(copy_backward、 transform、 replace_copy_if 等)
查看>>
ObjectAnimator属性动画应用demo
查看>>
HashMap与HashTable的区别
查看>>
黑色边影,
查看>>
Single Number II(LintCode)
查看>>