数据结构学习笔记——算法

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

算法定义

指令:能被人或者计算机装置执行。

算法是解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列,并且每条指令表达一个或者多个步骤。

算法的核心在于有限的指令序列

算法的特性

1、输入输出

算法具有零个或者多个输入。

算法至少要有一个或多个输出。

2、有穷性

指算法在执行有限的步骤之后,自动结束而不会出现无限循环,并且每一个步骤在可接受的时间内完成。

关键在与步骤有限

3、确定性

算法的每一个步骤都具有确定的含义,不会出现二义性。

4、可行性

算法的每一步都必须是可行的,也就是说,每一步都能够通过执行有限的次数完成。

意味着算法可以转化为程序上机运行,并得到正确结果。

算法设计要求

1、正确性

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

正确大致分为以下四个层次:

  • 算法程序没有语法错误;
  • 算法程序对于合法的输入数据能够产生满足要求的输出结果;
  • 算法程序对于非法输入数据能够得出满足规格说明的结果;
  • 算法程序对于精心选择、甚至刁难的测试数据都有满足要求的输出结果。

2、可读性

算法设计的另一目的是为了便于阅读、理解和交流。

3、健壮性

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

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

时间效率指的是算法的执行时间,执行时间越短,算法效率越高。

设计算法应该尽量满足时间效率高和存储量低的需求。

算法效率的度量方法

1、事后统计方法

缺点:

  • 先编好,再比较
  • 硬件条件影响
  • 测试数据设计困难

2、事前分析方法

事前分析估算方法:在计算机程序编制前,依据统计方法对算法进行估算。

一个程序运行时间主要取决于以下几个因素:

  • 算法采用的策略和方法;
  • 编译产生的代码质量;
  • 问题的输入规模;
  • 机器执行指令的速度。

抛开外部原因,影响算法执行效率主要依赖于 算法的好坏问题的输入规模

测定运行时间最可靠的方法是计算对运行时间有消耗的基本操作的执行次数。在分析算法执行效率时,我们主要关注于循环体,将循环体看作一个整体,忽略头尾循环判断的开销,算法主要就是1次和n次的差距。算法好坏显而易见。

算法运行时间:以基本操作的执行次数与输入规模关联起来,即基本操作的数量必须表示成输入规模的函数

函数渐进增长

给定两个函数 f(n) 和 g(n) ,如果存在一个整数N,使得对于所有的 n>N,f(n) 总是比 g(n) 大,那么,我们说 f(n) 的增长渐进快于 g(n) 。

在算法时间和问题规模的函数中,随着n的增大,不论+3还是+100,这些项其实不影响最终的算法变化,所以我们可以忽略这些加法常数

同时,与最高次项相乘的常数并不重要。

最高次项的指数越大,随着n的增长,结果也会变得增长得特别快。

综上,我们可以得出一个结论:

判断算法效率时,函数中的常数项和其他次要项常常可以忽略,而只关心最高阶项得阶数。

算法时间复杂度

1、定义

在进行算法分析时,语句总的执行次数 T(n) 是关于问题规模 n 的函数,进而分析 T(n) 随 n 的变化情况并确定 T(n) 的数量级。算法的时间复杂度,也就是算法的时间量度,记作 T(n) = O( f(n) ) 。它表示随问题规模 n 的增大,算法执行时间的增长率和 f(n) 的增长率相同,称作算法的渐近时间复杂度,简称为时间复杂度。其中 f(n) 是问题规模 n 的某个函数。

用大写 O( ) 来体现算法时间复杂度的记法,叫做大O记法

我们认为:随着 n 的增长, T(n) 增长最慢的算法为最优算法。

2、大O阶推导

  • 1、用常数1取代运行时间中的所有加法常熟;
  • 2、在修改后的运行次数函数中,只保留最高阶项;
  • 3、如果最高阶项存在且不是1,则去除与这个项相乘的常数。得到的结果就是大O阶。

3、常数阶

O(1)

与问题大小n无关,执行时间恒定的算法,称之为O(1)时间复杂度,又叫常数阶。

单纯的分支结构(不包含在循环结构中),其时间复杂度也是O(1) 。

4、线性阶

分析算法的复杂度,关键在于分析循环结构的运行情况。

O(n)

一般是单纯地、简单地循环结构。如 f(n) =3n+6 。

5、对数阶

O(log n)

一般是循环过程中,循环判断条件呈指数变化。

6、平方阶

O(n²)

嵌套循环中,内层循环条件初始值为外层条件当前值。

常见的时间复杂度

它们所消耗的时间从小到大依次是:

原文发布于微信公众号 - Android机动车(JsAndroidClub)

原文发表时间:2018-03-01

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器之心

资源 | Yoshua Bengio实验室MILA开放面向初学者的PyTorch教程

3066
来自专栏懒人开发

(7.7)James Stewart Calculus 5th Edition:Approximate Integration

黎曼求和,我们把对应的[a, b]分成n份,每份大概为 Δx = (b - a)/n 这个时候,有:

1813
来自专栏算法channel

这是一道算法面试题,不妨看看

要想从start 点到 finish 点,那么,必然经过 h1 或 h2 点,所以,问题转化为:求 start 点到 h1 点,或 start 点到 h2点的路...

924
来自专栏阿凯的Excel

剔除两侧极值求平均

祝新的一年,各位表亲财源广进! 不知道过年期间是否安好哇! 请各位表亲好好断句,不要说错话! 像小编这种英俊潇洒风流倜傥的,身边难免有很多选择。 我可以允...

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

非主流自然语言处理:大规模语料词库自动生成

一、前言   写这篇文时,突然想到一个问题,大家的词库都是从哪来的?   之所以会这么有些意外的问,是因为从没把词库当成个事儿:平时处理微博,就用程序跑一下微博...

64912
来自专栏C/C++基础

算法设计的方法

作用:要使计算机能完成人们预定的工作,首先必须为如何完成预定的工作设计一个算法,然后再根据算法编写程序。

883
来自专栏机器之心

业界 | 探索Siri背后的技术:将逆文本标准化(ITN)转化为标签问题

3004
来自专栏人工智能LeadAI

你听过算法也是可以贪心的吗?

贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解。 贪心算法...

3977
来自专栏逍遥剑客的游戏开发

Puyo-Puyo设计文档

2155
来自专栏大数据

算法:大O符号解释

O(n),O(1),O(log n)等大O符号被用来表示算法的效率。在这篇文章中,你会找到每个大O符号的例子和解释。

2751

扫码关注云+社区

领取腾讯云代金券