文档章节

算法学习笔记二---如何进行算法分析&渐近符号介绍

deepins
 deepins
发布于 2014/09/19 18:12
字数 1039
阅读 35
收藏 0

 

一、如何进行算法分析

算法分析指对一个算法需要的资源进行预测,其分析包括对一个算法的空间复杂度分析和时间复杂度分析。而随着硬件技术的飞速发展和成本的降低,我们更加关注算法在时间上的表现。

比较直观的做法是通过算法执行的时间来度量一个算法的时间上的效率。但这与执行算法的硬件和运行时的情境关系很大,不同机器、不同状态下的同一算法的运行时间都可能不同,所以这种算法是不科学的。

一个算法所需的时间应当是随着其输入规模增长的,而输入规模与特定具体问题有关。对大多数问题来说其最自然的度量就是输入中的元素个数。

算法的运行时间是指在特定输入时所执行的基本操作数。我们可以得到关于一个关于输入规模n的所需时间的函数。

然而可以进一步简化算法的时间分析,我们进行进一步抽象,首先,忽略每条语句的真实代价,通过运行时间的增长率来度量一个算法在时间方面的表现。我们只考虑公式的最高次项,并忽略它的常数系数。

通常,有三种情况的分析:

(1)最坏情况分析:这个是最常用的。通常我们想知道一个算法最糟能糟到什么情况,以此来分辨一个算法的好坏。对于升序排序算法,最糟糕的输入便是降序排列的数列。

(2)平均情况分析:这个也常用到。输入规模n下的期望时间。

(3)最好情况分析:比较少遇到。对于一个排序算法最好的情况无非输入已是排好序的。

二、要用到的渐近记号

所有记号都表示一切满足条件的函数的集合。

1、Θ记号  Θ(g(n)) = { f(n) : 若存在正常数c1,c2和n0,使对所有n>=n0时有0<=c1*g(n)<=f(n)<=c2*g(n)}

其效果相当于删除f(n)中的低阶项,并忽略最高阶项的系数。

2、Ο记号 Ο(g(n)) = { f(n) : 存在正常数c和n0,使对所有n>=n0,有0<=f(n)<=c*g(n) }

Ο记号在一个常数因子内给出某函数的一个上界。f(n) = Ο(g(n))表示f(n)是集合O(g(n))的一个元素。f(n) = Θ(g(n))隐含着f(n) = Ο(g(n)),因为Θ记号强于Ο记号。对f(n) = Ο(g(n))只能说明g(n)的某个常数倍是f(n)的渐近上界,而不反映该上界如何接近。Ο记号在用作对算法最坏情况运行时间的上界时就有对任意输入的运行时间的上界。

3、Ω记号 Ω(g(n)) = { f(n) : 存在正常数c和n0,使所有n>=n0有0<=c*g(n)<=f(n) }

Ω记号给出一个函数的渐近下界。

对于上面三种,有下面的定理:

对任意两个函数f(n)和g(n),f(n) = Θ(g(n))当且仅当f(n) = Ο(g(n))和f(n) = Ω(g(n)).

4、其它符号

ο记号:Ο记号提供的渐近上界可能是也可能不是渐近紧确的。2n^2 = Ο(n^2)是渐近紧确的,而2n = O(n^2)不是。而o记号用来表示非渐近紧确的。 o(g(n)) = { f(n) : 对任意正常数c,存在正常数n0,使对所有n>=n0,有0<=f(n)<=c*g(n) }

ω记号:ω记号与Ω记号的关系和o记号与Ο记号的关系一样,不在多说。


总之,可以这样理解,Θ记号相当于"=",Ο相当于“<=",Ω相当于”>=",o相当于“<",ω相当于">".这样理解只用于区别不同渐近记号间的关系,其实每个渐近记号为一个函数集合,而非两个数关系那样的。

 

本文转载自:http://deepin.iteye.com/blog/1340431

deepins
粉丝 8
博文 44
码字总数 0
作品 0
深圳
架构师
私信 提问
《数据结构》学习笔记二:算法(二)

继续上节的学习,我们在这一篇文章里把“算法”这一章内容学习完。 本节解决问题: 算法的好坏到底是如何评估的? 知识点: 1.函数的渐进增长 2.算法的时间复杂度 3.常见的时间复杂度 4.算法...

小曼Study
2018/10/12
0
0
1个掷硬币问题,4个Python解法:读书笔记

关键词:统计,概率,机器学习,Pandas, Numpy, sympy scipy 预计阅读时间-10分钟 我在学习机器学习算法和玩Kaggle 比赛时候,不断地发现需要重新回顾概率、统计、矩阵、微积分等知识。如果按...

王勇
2017/12/04
0
0
AI学习者必备 | 圣母大学公开统计计算课程讲义(视频+PPT+作业)

翻译 | AI科技大本营(微信ID:rgznai100,点击查看AI科技大本营更多干货文章) 参与 | 刘畅 近日,圣母大学(University of Notre Dame)公开了一门统计学课程资源,包括:课程笔记和授课视频...

AI科技大本营
2018/01/02
0
0
机器学习框架ML.NET学习笔记【3】文本特征分析

一、要解决的问题 问题:常常一些单位或组织召开会议时需要录入会议记录,我们需要通过机器学习对用户输入的文本内容进行自动评判,合格或不合格。(同样的问题还类似垃圾短信检测、工作日志...

seabluescn
05/30
0
0
随笔:估算程序算法复杂度的理解

大体分为:事前估算(设计算法之前就估算此算法性能)和事后估算(运行后,通过收集数据) 直觉上以为是事后估算为主,毕竟,实践是检验真理的标准嘛。事后收集数据才是比较靠谱的。 不过,想法错...

wangtaotao
2014/04/10
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Spring Boot + Mybatis-Plus 集成与使用(二)

前言: 本章节介绍MyBatis-Puls的CRUD使用。在开始之前,先简单讲解下上章节关于Spring Boot是如何自动配置MyBatis-Plus。 一、自动配置 当Spring Boot应用从主方法main()启动后,首先加载S...

伴学编程
昨天
7
0
用最通俗的方法讲spring [一] ──── AOP

@[TOC](用最通俗的方法讲spring [一] ──── AOP) 写这个系列的目的(可以跳过不看) 自己写这个系列的目的,是因为自己是个比较笨的人,我曾一度怀疑自己的智商不适合干编程这个行业.因为在我...

小贼贼子
昨天
7
0
Flutter系列之在 macOS 上安装和配置 Flutter 开发环境

本文为Flutter开发环境在macOS下安装全过程: 一、系统配置要求 想要安装并运行 Flutter,你的开发环境需要最低满足以下要求: 操作系统:macOS(64位) 磁盘空间:700 MB(不包含 IDE 或其余...

過愙
昨天
6
0
OSChina 周六乱弹 —— 早上儿子问我他是怎么来的

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @凉小生 :#今日歌曲推荐# 少点戾气,愿你和这个世界温柔以待。中岛美嘉的单曲《僕が死のうと思ったのは (曾经我也想过一了百了)》 《僕が死の...

小小编辑
昨天
2.7K
16
Excption与Error包结构,OOM 你遇到过哪些情况,SOF 你遇到过哪些情况

Throwable 是 Java 中所有错误与异常的超类,Throwable 包含两个子类,Error 与 Exception 。用于指示发生了异常情况。 Java 抛出的 Throwable 可以分成三种类型。 被检查异常(checked Exc...

Garphy
昨天
42
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部