算法设计与分析 李清勇 教授 办公室:第九教学楼北201.

Slides:



Advertisements
Similar presentations
基本概論 Basic concepts.
Advertisements

第十章 儿童性别角色社会化.
奥田2016年经销商大会传播方案.
政府採購法規概要 報告人:杜國正 行政院公共工程委員會企劃處.
親愛的老師您好 感謝您選用本書作為授課教材,博碩文化準備本書精選簡報檔,特別摘錄重點提供給您授課專用。 說明: 博碩文化:
计算学科的基本问题 本章首先介绍一个对问题进行抽象的典型实例——哥尼斯堡七桥问题。然后,通过“梵天塔”问题和“停机问题”分别介绍学科中的可计算问题和不可计算问题。从“梵天塔”问题再引出算法复杂性中的难解性问题、P类问题和NP类问题,证比求易算法,P=NP是否成立的问题。
请说出牛顿第一定律的内容。.
之 魔 析 妖 鬼 解 怪 大 沈家仪小组出品.
经济新闻集锦.
邰港生物科技公司參訪.
数据结构 第一章 绪论.
C#程序设计案例教程 第3章 程 序 结 构.
第二章 项目一:企业厂区与车间平面设计 1.
算法设计与分析 第二章 递归与分治策略 杨圣洪.
武进区三河口中学欢迎您.
AI人工智慧報告 黑白棋 班級:資工四乙 學號:498G0009 姓名:盧冠妤.
共产党员致力 新疆油田信息化建设 数据公司信息业务党支部 2013年6月.
算法设计与分析 Algorithm Design and Analysis
第十一章 真理与价值 主讲人:阎华荣.
Performance Evaluation
第7章 行政监督.
蔬菜常见缺素症状及防治方法 龙岩市科技局.
第七章 固 定 资 产.
第九章 长期资产及摊销 2017/3/21.
数据结构——树和二叉树 1/96.
第五章 树 东南大学计算机学院 方效林 本课件借鉴了清华大学殷人昆老师 和哈尔滨工业大学张岩老师的课件.
雷 霆 战 机 By—谷恩轩&余万全.
一 二 三 四 五 六 七 项目建设总体情况 建设工作机制与举措 项目建设进展 建设经费投入与使用 贡献与示范 典型案例
節日狂歡轟炸耳仔.
92-90數學課程綱要比較 -- 不含數與計算 台北市立師範學院 數學資訊教育系副教授 李源順.
数据结构与算法 数据结构与算法实验
C++程序设计 王希 图书馆三楼办公室.
行政院國軍退除役官兵輔導委員會 嘉義榮民醫院.
第5章 函数与模块化设计 学习目的与要求: 掌握函数的定义及调用方法 理解并掌握参数的传递方法 理解函数的嵌套与递归调用
If … else 選擇結構 P27.
第 1 章 演算法分析.
计算复杂性和算法分析 计算机科学导论第六讲
程式設計實作.
第12章 從C到C++語言 12-1 C++語言的基礎 12-2 C++語言的輸出與輸入 12-3 C++語言的動態記憶體配置
第四章 串.
$10 可空类型.
第 4 章 递 归 教学要求 本章重点 了解递归算法的概念与递归设计要领 掌握应用递归算法求解排序与选择、实现排列组合等典型案例
计算机算法设计与分析(第3版) 王晓东 编著 电子工业出版社.
公立學校教職員退休資遣撫卹條例重點說明 苗栗縣政府人事處編製 主講人:陳處長坤榮 107年5月2日.
鄧姚文 資料結構 第一章:基本概念 鄧姚文
鄧姚文 資料結構 第五章:遞迴 鄧姚文
Week 2: 程式設計概念與 演算法的效能評估
第1章 绪论 2019/4/16.
第5章 回溯法 欢迎辞.
數學遊戲一 河內塔 (Tower of Hanoi)
資料結構與演算法 第一章 基本概念 徐熊健 資料結構與演算法 徐熊健.
数 据 结 构 与 算 法.
第1章 绪论(二) 教学目标 理解算法的特性及评价标准 掌握算法时间复杂度和空间复杂度的分析方法 1/
程式的時間與空間 Time and Space in Programming
講師:郭育倫 第2章 效能分析 講師:郭育倫
C程序设计.
<编程达人入门课程> 本节内容 为什么要使用变量? 视频提供:昆山爱达人信息技术有限公司 官网地址: 联系QQ:
第二章 Java语法基础.
資料結構簡介 綠園.
演算法的效率分析.
演算法分析 (Analyzing Algorithms)
第二章 类型、对象、运算符和表达式.
淘汰與搜尋法 /5/9 演算法 _ 第四章.
——向刑事案件被告人家属调查取证的伦理性讨论
#include <iostream.h>
第四章 函数 丘志杰 电子科技大学 计算机学院 软件学院.
第二章 Java基本语法 讲师:复凡.
與家庭工作〜 家訪技巧 方瓊聆社工師      高雄市學生輔導諮商中心
第1章 数据结构基础概论 本章主要介绍以下内容 数据结构研究的主要内容 数据结构中涉及的基本概念 算法的概念、描述方法以及评价标准.
基本資料型態 變數與常數 運算子 基本的資料處理 授課:ANT 日期:2014/03/03.
Presentation transcript:

算法设计与分析 李清勇 教授 办公室:第九教学楼北201

引言 1. 评价指标 2. 交流符号 为什么需要这个概念—算法复杂度? 最大和连续子数列问题: 算法1 算法2 算法3 算法4 算法1 算法2 算法3 算法4 2. 交流符号 Boss:针对这个问题你们算法的性能怎么样? Developer 1:A算法复杂度是??? Developer 2:B算法复杂度是???

算法复杂度 ─ 直观定义 算法复杂度是算法运行所需要的计算机资源的量,需要时间资源的量称为时间复杂性,需要的空间资源的量称为 空间复杂性。 时间复杂度和空间复杂度是只依赖于算法求解的问题规模和算法输入的函数 𝑁、𝐼分别表示算法求解的问题规模和算法输入,则算法的时间复杂度𝑇和空间复杂度𝑆可以分别表示为: 𝑇=𝑇(𝑁,𝐼) 𝑆=𝑆(𝑁,𝐼)

问题规模 迷宫问题: 在一个N*N的迷宫中,求解从入口到出口的路径,如果不存在路径则返回0。 问题的规模: N=2 VS N=10000

输入实例 迷宫问题: 问题规模N=10000时,算法的输入: 在一个N*N的迷宫中,求解从入口到出口的路径,如果不存在路径则返回0。 输入1:没有路径,且入口即被障碍包围 输入2:没有路径,但是在出口处才判定

直观定义的困境 影响算法执行时间的因素: 计算机配置 问题规模 输入实例 时间复杂度不应该是在特定计算机上求解某一个输入实例所需要的运行时间;而应该是一个不依赖于计算机配置、问题规模和输入实例的抽象表示。

算法复杂度分析 ─ 指令抽象 T(N, I) 表示特定算法在一台抽象的计算机上运行所需要的时间。 K个元运算,O1, O2, …, Ok, 运行一次所需时间为 t1, t2, …, tk; 统计Oi的调用次数为ei,ei = ei(N, I); 因此,T(N, I) = ∑tiei(N, I)。

Swap 算法复杂度分析 ─ 指令抽象 冒泡排序算法(升序排列) 2. 1 图像 如果输入为 [1, 2, 3, 4, 5], void sort(int *pValues, int iDim) { for (int i = 0; i < iDim; i++) for (int j = 1; j < iDim – i; j++) if (pValues[j] < pValues[j -1]) int iTemp = pValues[j]; pValues[j] = pValues[j - 1]; pValues[j - 1] = iTemp; } 如果输入为 [1, 2, 3, 4, 5], 需要0次Swap操作 如果输入为[5, 4, 3, 2, 1], 需要10次Swap操作 Swap 不可能对规模为N的每一种合法输入都统计Swap,需合理的简化

算法复杂度分析 ─ 输入特化 最坏情况下的时间复杂性: 最好情况下的时间复杂性: 平均情况下的时间复杂性: 其中 𝐷 𝑁 是规模为𝑁的合法输入的集合; 𝐼 ∗ 是 𝐷 𝑁 中使𝑇(𝑁,𝐼)达到 𝑇 𝑚𝑎𝑥 (𝑁)的合法输入; 𝐼 是 𝐷 𝑁 中使𝑇(𝑁,𝐼)达到 𝑇 𝑚𝑖𝑛 (𝑁)的合法输入;而𝑃(𝐼)是在算法的应用中出现输入I的概率

Swap 时间复杂度表示— 输入特化 冒泡排序算法(升序排列) T(N)的表达式比较复杂,需合理的简化! T(N) = (N-1) + … + 1 = N(N-1)/2 = 0.5N2 – 0.5N void sort(int *pValues, int n) { for (int i = 0; i < n; i++) for (int j = 1; j < n – i; j++) if (pValues[j] < pValues[j -1]) int iTemp = pValues[j]; pValues[j] = pValues[j - 1]; pValues[j - 1] = iTemp; } Boss:这个算法的复杂度怎么样? Developer:它的复杂度是0.5N2 – 0.5N Boss:神马?囧 N充分大时,比如𝑁= 10 10 , 有0.5 𝑁 2 ≫ 0.5𝑁,以至于0.5N可以忽略不计。 Swap T(N)的表达式比较复杂,需合理的简化!

时间复杂度表示—函数简化 例1:𝑇 𝑁 =10 𝑁 2 +100𝑁+10000 𝑇 ′ 𝑁 =10 𝑁 2 对于算法A的复杂性函数𝑇(𝑁),如果存在𝑇′(𝑁) ,使得当𝑁→∞时有 (𝑇 𝑁 −𝑇′(𝑁)) 𝑇(𝑁)→0 ,那么就称𝑇′(𝑁)为算法A当𝑁→∞的渐近复杂性。 例1:𝑇 𝑁 =10 𝑁 2 +100𝑁+10000 𝑇 ′ 𝑁 =10 𝑁 2 例2:𝑇 𝑁 = 2 𝑁 + 𝑖=1 100 𝑖∗ 𝑁 𝑖 +1000000000000 𝑇 ′ 𝑁 = 2 𝑁 𝑇′(𝑁)是𝑇(𝑁)略去低阶项所留下的主项,表达简单 如果两个算法的渐近复杂性的阶不相同,那么只要确定出各自的阶就可以判断哪一个算法效率高 阶跟𝑇′(𝑁)中的常数因子没有关系, 𝑇′(𝑁)可进一步简化,省略常数因子

时间复杂度记号 时间复杂度的记号包括:O Ω Θ

时间复杂度记号O O的定义: 注意: O得到的只是一个充分大的上界,这个上界的阶越低则评估就越精确,结果就越有价值! 设f(N)和g(N)是定义在正数集上的正函数,如果存在正的常数C和自然数N0,使得当N≥N0时有f(N) ≤Cg(N),则称函数f(N)当N充分大时上有界,g(N)是f(N)的一个上界,记为f(N)=O(g(N)),即f(N)的阶不高于g(N)的阶。 Cg(N) f(N) 注意: O得到的只是一个充分大的上界,这个上界的阶越低则评估就越精确,结果就越有价值! g(N) N0

例子1 证明: 给定多项式函数:𝑇 𝑛 = 𝑎 𝑘 𝑛 𝑘 + 𝑎 𝑘−1 𝑛 𝑘−1 +… + 𝑎 1 𝑛+ 𝑎 0 , 给定多项式函数:𝑇 𝑛 = 𝑎 𝑘 𝑛 𝑘 + 𝑎 𝑘−1 𝑛 𝑘−1 +… + 𝑎 1 𝑛+ 𝑎 0 , 试证明 𝑇(𝑛)= O(𝑛^𝑘) 证明: 选择 𝑛 0 =1,C= 𝑎 𝑘 + 𝑎 𝑘−1 +…+ 𝑎 1 + 𝑎 0 则需要证明 𝑛≥1,𝑇(𝑛)≤𝐶 𝑛 𝑘 对于任意𝑛, 如果𝑛≥1,则: 𝑪 ∙𝒏 𝒌 = 𝑎 𝑘 𝑛 𝑘 + 𝑎 𝑘−1 𝑛 𝑘 +…+ 𝑎 1 𝑛 𝑘 + 𝑎 0 𝑛 𝑘 ≥ 𝑎 𝑘 𝑛 𝑘 + 𝑎 𝑘−1 𝑛 𝑘−1 +…+ 𝑎 1 𝑛+ 𝑎 0 ≥ 𝑎 𝑘 𝑛 𝑘 + 𝑎 𝑘−1 𝑛 𝑘−1 +…+ 𝑎 1 𝑛+ 𝑎 0 =𝑻(𝒏)

例子2 证明(反证法): 给定多项式函数:𝑇 𝑛 = 𝑎 𝑘 𝑛 𝑘 , 试证明 𝑇 𝑛 ≠ O( 𝑛 𝑘−1 ) 给定多项式函数:𝑇 𝑛 = 𝑎 𝑘 𝑛 𝑘 , 试证明 𝑇 𝑛 ≠ O( 𝑛 𝑘−1 ) 证明(反证法): 假设 𝑇 𝑛 = O( 𝑛 𝑘−1 ) , 则存在 𝑛 0 和C,对于任意𝑛,当𝑛≥ 𝑛 0 时满足: 𝑇 𝑛 ≤𝐶 𝑛 𝑘−1 ,即 𝑎 𝑘 𝑛 𝑘 ≤𝐶 𝑛 𝑘−1 消除 𝑛 𝑘−1 ,得到 𝑛≤ 𝐶 𝑎 𝑘 ,与条件𝑛≥ 𝑛 0 矛盾!

运算法则 根据O的定义,容易证明它有如下运算规则: O(f)+O(g)=O(max(f,g)); 2) O(f)+O(g)=O(f+g); 4) 如果g(N)=O(f(N)),则O(f)+O(g)=O(f); 5) O(Cf(N))=O(f(N)),其中C是一个正的常数; 6) f=O(f)。 在课堂推理规则(2)

时间复杂度记号O 𝑓 𝑛 =3𝑛+2, 𝑔 𝑛 =𝑛 𝑓 𝑛 =6∗ 2 𝑛 + 𝑛 2 , 𝑔 𝑛 = 2 𝑛 𝑓 𝑛 = 𝑛 16 +3∗ 𝑛 2 , 𝑔 𝑛 = 2 𝑛

时间复杂度记号 Ω的定义: 如果存在正的常数C和自然数N0,使得当NN0时有f(N)Cg(N),则称函数f(N)当N充分大时下有界,且g(N)是它的一个下界,记为f(N)=Ω(g(N)),即f(N)的阶不低于g(N)的阶。 Θ的定义:定义f(N) = Θ(g(N)) 当且仅当 f(N)=O(g(N)) 且f(N)= Ω(g(N)),此时称f(N)与g(N)同阶。 定理1:对于多项式函数 𝑓 𝑁 = 𝑎 𝑚 𝑁 𝑚 + 𝑎 𝑚−1 𝑁 𝑚−1 +⋯+ 𝑎 1 𝑁+ 𝑎 0 ,如果 𝑎 𝑚 >0,则有: 𝑓 𝑁 =𝑂( 𝑁 𝑚 ),𝑓 𝑁 =𝛺( 𝑁 𝑚 ),𝑓 𝑁 =𝛩( 𝑁 𝑚 ) 简单说明即可,它只不过是O的一个补充 10/25

时间复杂度类别 按照O(f)函数形式把时间复杂度分为两类: 多项式复杂度算法,形如:O(nc) 指数复杂度算法, 形如:O(cn) 举例说明时间复杂性: n=1024时,单个加法运算 O(logn)和O(n)各自所需要的时间; 画出各个函数的草图 1-n的全排列是一个O(n !)问题 O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)…<O(cn)<O(n!)<O(nn)

时间复杂度类别比较

非递归算法时间复杂性分析 1 确定关键操作 可以是高级程序设计语言中的赋值、比较、算术运算、逻辑运算、读写单个常量或单个变量等操作(一般被看作是基本操作,并约定所用的时间都是一个单位);也可以是由常数个基本操作构成的程序块。 计算关键操作总的执行步数 一般是数列和的形式。 2 求解其渐进阶,并用O(.)表示 3

实例--1 问题描述: 算法描述: 给定数组A(长度为n)和数t,判断数组A中是否包含t? 时间复杂度:O(𝑁) bool isExist(float* iArray, int n, float t) { for (int i = 0; i < n; i++){ if (iArray[i] == t) return true; } return false; 时间复杂度:O(𝑁)

实例--2 问题描述: 算法描述: 给定数组A和B(长度为n)和数t,判断数组A或者B中是否包含t? 时间复杂度:O(𝑁) bool isExist(float* iArrayA, float* iArrayB, int n, float t) { for (int i = 0; i < n; i++){ if (iArrayA[i] == t) return true; } if (iArrayB[i] == t) return false; 时间复杂度:O(𝑁) 想想与例1的区别哦!!

实例--3 问题描述: 算法描述: 给定数组A和B(长度为n),判断数组A和B中是否包含相同元素? 时间复杂度:𝑂(𝑁²) bool isCommon(float* iArrayA, float* iArrayB, int n) { for (int i = 0; i < n; i++){ for (int j = 0; j < n; j++) if (iArrayA[i] == iArrayB[j]) return true; } return false; 时间复杂度:𝑂(𝑁²)

实例--4 问题描述: 算法描述: 给定数组A(长度为n),判断数组A中是否包含重复元素? 时间复杂度:𝑂(𝑁²) 想想与例3的区别哦!! bool isDuplicate(float* iArrayA, int n) { for (int i = 0; i < n; i++){ for (int j = i + 1; j < n; j++) if (iArrayA[i] == iArrayA[j]) return true; } return false; 想想与例3的区别哦!! 时间复杂度:𝑂(𝑁²)

实例--5 问题描述: 给定升序排列的整数数组A(长度为n)和整数x,判断数组A中是否包含元素x,如果存在则返回其位置,否则返回-1? 算法描述: int BinarySearch(int* iArrayA, int n, int x) { int left=0; int right=n-1; while(left<=right) int middle=(left+right)/2; if(x== iArrayA[middle]) return middle; if(x> iArrayA[middle]) left=middle+1; else right=middle – 1; } return –1; //未找到x 时间复杂度:O(log⁡(𝑁))

递归算法时间复杂性分析 1 分析递归程序的结构,确定每一逻辑块的时间复杂性 非递归的程序块(或者子函数)用非递归方法分析其复杂性;递归函数的复杂性则跟据其输入规模递归地表示。 构造复杂性函数的递推方程 2 3 求解递归方程和渐进阶,并用O(.)表示

实例--1 问题描述: 算法描述: 求整数n的阶乘。 时间复杂度:O(𝑁) long FN( long n ) { if (n<=1) return 1; return n * FN(n-1); } 时间复杂度:O(𝑁)

实例--2 问题描述: 算法描述: 时间复杂度:O( 2 𝑁 ) 三根杆子A,B,C。A杆上有N个(N>1)穿孔圆盘,盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆: 每次只能移动一个圆盘; 大盘不能叠在小盘上面。 A B C 算法描述: int Hanoi( int n, int a, int b, int c) { if (n<=0) return 0; Hanoi( n-1, a, c, b ); Move( a, c ); Hanoi( n-1, b, a, c ); return 1; } 时间复杂度:O( 2 𝑁 )

内存算法 外存算法 编外 在大数据情景下,算法可能需要处理的数据规模是TB级别或者以上,无 法在内存中存储和处理所有数据; 数据 I/O将占用大部分的时间,内存是随机存储,外存是顺序存储。 在内存中取数据类似于在身边桌子上拿一个东西;在外存中取数据类似于坐飞机去美国的某个桌子上取数据。机械手臂先把磁头移动到相应磁道,然后主轴旋转把相应磁区转到磁头下面进行读取。

编外 内存算法 外存算法 分布式算法 在分布式情景下,通信模块 将占用大部分的时间

作业 试证明 2 𝑁+10 =𝑂 2 𝑁 。 试证明 2 10𝑁 ≠𝑂 2 𝑁 。 给定正函数𝑓 𝑁 ,𝑔(𝑁),试证明 max 𝑓,𝑔 =𝑂(𝑓 𝑁 +𝑔(𝑁))。

谢谢 THANKS