算法(1)

算法定义:算法是解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列,并且每条指令表示一个或多个操作。 通俗来讲:算法是描述解决问题的方法

一、算法的特性

算法五个基本特征:

  • 输入、输出、有穷性、确定性和可行性

1、输入输出

  • 算法具有零个或多个输入 大多数算法输入参数都是必要的,但类似打印"Hello World",就不用输入参数
  • 算法至少有一个或多个输出 算法一定需要输出,不需要输出,要算法就没意义了。输出形式可以回打印输出,也可以是返回一个或多个值

2、有穷性

  • 指算法在执行有限步骤后,自动结束而不会无限循环,并且每一步骤在可接受的时间内完成 写一个算法,计算机需要算上十几二十年,那算法就没意义了

3、确定性

  • 算法的每一步都具有确定的含义,没有歧义 算法在一定条件下,只有一条执行路径,相同的输出只有唯一的输出结果

4、可行性

  • 算法的每一步都必须可行,即每一步都能通过执行有限次数完成 可行性意味算法可以转换为程序上机运行,并得到正确的结果。
二、算法设计的要求

1、正确性

  • 正确性是指算法至少应该具有输入、输出和加工处理无歧义性、能正确反映问题的需求,能够得到问题的正确答案

2、可读性

  • 算法设计的另一目的是为了便于阅读、理解和交流。 写代码,一方面是为了让计算机执行,但还有一个重要目的是便于他人阅读,让人理解和交流,可读性是算法好坏的一个重要标识。

3、健壮性

  • 当输入数据不合法时,算法也能做出相关处理,而不是产生异常或莫名其妙的结果

4、时间效率高和存储量低

  • 花最少的钱,用最短的时间,办最大的事,算法也是一样的思想,最好用最少的存储时间,花最少的时间,办成同样的事。
三、算法效率的度量方法

1、事后统计方法

  • 主要是通过设计好的测试程序和数据,利用计算机计时器对不同算法编制的程序的运行时间进行比较,从而确定算法效率的高低 有很大缺陷,不予采纳

2、事前分析估算方法

  • 事前分析估算方法:在计算机程序编制前,一句统计方法对算法进行估算。 程序在计算机上运行时所消耗的时间取决下列因素: (1)算法采用的策略、方法。 (2)编译产生的代码质量。 (3)问题的输入规模。 (4)机器执行指令的速度。 第1条当然是算法好坏的根本,第二条要由软件来支持,第4条要看硬件性能。也就是说,抛开这些与计算机硬件、软件有关的因素,一个程序的运行时间,依赖于算法的好坏和问题的输入规模。所谓问题输入规模是指输入量的多少。 接下来看两个例子 第一种算法:
    int i, sum = 0, n = 100;        /*执行1次*/
    for (i = 1; i <= n; i++) {      /*执行n+1次*/
        sum = sum + i;              /*执行n次*/
    }
    printf("%d", sum);              /*执行1次*/

第二种算法:

    int sum = 0, n = 100;       /*执行1次*/
    sum = (1 + n) * n/2;        /*执行1次*/
    printf("%d", sum);          /*执行1次*/

显然,第一种算法,执行了1+(n+1)+n+1 = 2n+3次;而第二种算法,是1+1+1=3次,算法好坏显而易见。 延伸一下上面例子:

    int i, j, x = 0, sum = 0, n = 100;    /*执行1次*/
    for (i = 1; i < n; i++) {
        for (j = 1; j <= n; j++) {
            x++;                          /*执行n*n次*/
            sum = sum + x;
        }
    }
    printf("%d", sum);                    /*执行1次*/

这个例子中,i从1到100,每次都要让j循环100次,而当中的x++和sum = sum + x; 其实就是1+2+3+...+10000,也就是100²,所以循环部分的代码整体需要执行n²(忽略循环头尾的开销)次。这个算法的执行时间随着n的增加将远远多于前面两个。 分析一个算法的运行时间时,重要的是把基本操作的数量与输入规模关联起来,即基本操作的数量必须表示成输入规模的函数

算法操作

随着n值得越来越大,它们在时间效率上的差异也就越来越大。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器学习和数学

[Tensorflow] TensorFlow之Hello World!(1)

哇!今天挺开心的,30天的时间,19篇文章,2459人阅读,5313人次阅读!今天开通的原创标识,恩!除了激动,就是非常感谢大家的支持!感谢大家的支持!大家的支...

35860
来自专栏编程心路

人人都可以用C语言写推箱子小游戏

C语言,作为大多数人的第一门编程语言,重要性不言而喻,很多编程习惯,逻辑方式在此时就已经形成了。这个是我学习 C语言 后写的推箱子小游戏,自己的逻辑能力得到了提...

1.3K40
来自专栏javascript趣味编程

3.1 Contour绘制

首先一起学习利用百度的开源项目绘制contour,百度搜索“echarts heatmap”,找到热力图的一个案例(http://echarts.baidu.c...

14000
来自专栏机器之心

学界 | 为代码自动添加注释,让 Java 程序的阅读和开发更高效

37570
来自专栏大数据挖掘DT机器学习

R语言数据处理:飞机航行距离与到达延误时间有什么关系??

数据分析有一半以上的时间会花在对原始数据的整理及变换上,包括选取特定的分析变量、汇总并筛选满足条件的数据、排序、加工处理原始变量并生成新的变量、以及分组汇总数...

38740
来自专栏机器之心

教程 | 如何使用JavaScript构建机器学习模型

选自:hackernoon 作者:Abhishek Soni 参与:李泽南 目前,机器学习领域建模的主要语言是 Python 和 R,前不久腾讯推出的机器学习框...

34660
来自专栏PPV课数据科学社区

数据挖掘系列(4)使用weka做关联规则挖掘

前面几篇介绍了关联规则的一些基本概念和两个基本算法,但实际在商业应用中,写算法反而比较少,理解数据,把握数据,利用工具才是重要的,前面的基础篇是对算法的理解,这...

53060
来自专栏吕晟的专栏

机器学习库初探之 TensorFlow

什么是TensorFlow?TensorFlow™ 是一个采用数据流图(data flow graphs),用于数值计算的开源软件库。节点(Nodes)在图中表...

78310
来自专栏决胜机器学习

机器学习(十四) ——朴素贝叶斯实践

机器学习(十四)——朴素贝叶斯实践 (原创内容,转载请注明来源,谢谢) 一、垃圾邮件分类 垃圾邮件分类,即通过读取邮件的内容,并打上标记其是垃圾邮件或者是正常...

36570
来自专栏ATYUN订阅号

使用Tensor2Tensor和10行代码训练尖端语言翻译神经网络

有许多库可以帮助人们构建深度学习应用程序,但如果想使用最新架构的最先进模型和最少的代码,有这样一个API脱颖而出:Google的Tensor2Tensor。我通...

33730

扫码关注云+社区

领取腾讯云代金券