Amortized Analysis Michael Tsai 2013/11/14.

Slides:



Advertisements
Similar presentations
105 年大專程度義務役 預備軍官預備士官考選 說 明 會說 明 會 報告人:師大軍訓室 林鴻禧先生.
Advertisements

文学灵感论 蓦然回首,那人却在灯火阑珊处 ……. 生活中、科学中的灵感 运动鞋 电梯 阿基米德与皇冠 牛顿的三大定律.
—— 海淀区高三化学《考试说明》解读 2015 年 1 月 29 日 学习《考试说明》 备考理综化学.
不知者無罪嗎 ? 【本報台北訊】國內知名大學胡姓研究 生進口豬籠草在網路上販售,涉嫌違反 植物防疫檢疫法,胡姓研究生表示不知 道豬籠草是違禁品並當場認錯道歉 台北地檢署檢察官念他初犯,昨 天處分緩起訴,但命他繳交六萬 元緩起訴處分金作公益。 豬籠草有潛移性線蟲寄生,一旦植物感 染後,輕則枯萎凋零,重則危害農業經.
Course 1 演算法: 效率、分析與量級 Algorithms: Efficiency, Analysis, and Order
報告書名:父母會傷人 班級:二技幼四甲 姓名:吳婉如 學號:1A2I0034 指導老師:高家斌
基本概論 Basic concepts.
第九章 認識勞退新制及因應之道 大葉大學 助理教授 邱祈豪.
数据结构 杨鹏宇 QQ: 版权所有,转载或翻印必究
一、市场营销调研综述 二、市场营销资料的收集 三、问卷设计 四、抽样设计 五、分析资料
第一章 資料結構導論 1-1 資料結構簡介 1-2 認識程式設計 1-3 演算法效能分析 1-4 物件導向程式設計與Java.
媽,我們真的不一樣 青少年期與中年期 老師: 趙品淳老師 組員: 胡珮玟4A1I0006 馬菀謙4A1I0040
Cuckoo Filter & Bloom Filter 比较
第1章第3节 量化研究与质化研究 案例1:关于中学思想政治教师专业发展现状和需求的调查研究
天 狗 郭沫若.
班級:二幼三甲 姓名:郭小瑄 、 詹淑評 學號:1A2I0029 、1A2I0025
班級:行流四甲 組員:497D0004何筱瑩 497D0016鄧宜欣 497D0044呂亭儀 497D0056黃 琪 497D0063賴依淩
2012年第14届 全国大学生英语竞赛题型介绍.
数据结构(C语言版) Data Structure
指導老師:陳韻如 姓名:吳宜珊 學號:4A0I0911 班級:幼保二乙
Performance Evaluation
第三章 鏈結串列 Linked List.
Recurrences 給定T(n)=T(n/2) + O(n) 我們該如何得到 T(n) = O(nlogn)?
傳統童玩遊戲創新 組別:第八組 班級:幼保二甲 組員: 4A0I0005柯舒涵 4A0I0011謝孟真
网络信息资源的开发与设计 主讲教师 罗双兰 广西师范大学教育科学学院.
主題三 現代公民與經濟生活 錢 「經濟就是生活」 什麼是「經濟」? 社會科學: 研究人的行為與社會關係 柴米油鹽醬醋茶,食衣住行育樂
我的心得報告 經過篩選,挑中我們 十多位學生由學校推薦進入公司,開始他們的學習之旅 學習的過程中有想像不到的意外驚喜
讚美得勝的生活 張譽騰傳道.
计算机导论 ——软件部分 巢爱棠 办公室:1208.
Tree(樹) 什麼是「樹」? 「樹」的範例 「樹」的定義 「樹」的表示法.
Operating System Concepts 作業系統原理 Chapter 3 行程觀念 (Process Concept)
主讲人: 吕敏 { } Spring 2012 ,USTC 算法基础 主讲人: 吕敏 { } Spring 2012 ,USTC.
佇列與推疊 (Queue and Stack)
Chap 3 堆疊與佇列 Stack and Queue.
經濟學100 第九章 經濟成長與景氣循環.
Course 4 搜尋 Search.
生產與作業管理 Chapter 15 物料需求管理 第七組組員: M 曾子鴻 M 李正文
第 10 章 生產管理 授課教師:__________ 工業工程與管理概論 陳潭,洪堯勳,姚銘忠,黃欽印 著 前程文化出版.
Transact-SQL 語言設計教學.
Graph 2 Michael Tsai 2012/5/1 連載: 學生上課睡覺姿勢大全
Chapter 3 行程觀念 (Process Concept)
数据挖掘: 概念和技术 — Chapter 6 — ©张晓辉 复旦大学 (国际)数据库研究中心
第3章 栈和队列(一).
第三章 栈和队列.
String Matching Michael Tsai 2012/06/04.
第三章 栈和队列.
樹 2 Michael Tsai 2013/3/26.
Abstract Data Types 抽象数据类型 Institute of Computer Software 2019/2/24
感謝同學們在加分題建議. 我會好好研讀+反省~
第二章 商业银行资本管理.
Week 2: 程式設計概念與 演算法的效能評估
第1章 绪论 2019/4/16.
Linked Lists Prof. Michael Tsai 2013/3/12.
Hashing Michael Tsai 2013/06/04.
String Matching Michael Tsai 2013/05/28.
An Introduction to Communication Complexity
講師:郭育倫 第2章 效能分析 講師:郭育倫
Disjoint Sets Michael Tsai 2013/05/14.
演算法分析 (Analyzing Algorithms)
红利、年金、满期金自动转入聚宝盆,收益有保底,升值空间更大
第 六 讲 栈和队列(一).
作业3、4、6、7 俞天灿.
Hashing Michael Tsai 2017/4/25.
Open topic2: 大O( Θ ,Ω)和小o( θ ,ω)有什么区别? 3/19/18 黄秉焜
介入及追蹤紀錄表 編號: 姓/稱謂: 初次103年 月 日 追蹤 月 日 問題型態 (可複選) □ 1. 覺得西藥都很傷胃
Resources Planning for Applied Research
2012 程式設計比賽 Openfind 天使帝國 v2.0 (蓋亞的紋章).
Chapter4工作分析與工作評價 第一節 工作分析 第二節 工作評價.
算法基础习题课2 助教:刘倩玉.
Presentation transcript:

Amortized Analysis Michael Tsai 2013/11/14

為什麼需要Amortized Analysis O(f(n)) running time n operations =O(n f(n)) ?? 估得太鬆了!

Amortized Analysis Amortized: 可以想成是把一連串的operation一起考慮它的花費(也就是執行時間) Reduce or extinguish (a debt) by money regularly put aside 攤銷 可以想成是把一連串的operation一起考慮它的花費(也就是執行時間) 一起考慮的時候有時候估計比較準確(bound比較緊)

Aggregated Analysis T(n): n個operation最差狀況下所需花的時間 因此, 每個operation攤分的所需時間(amortized cost)為T(n)/n 在aggregated analysis中, 我們不區分不同operation的所需時間 (也就是amortized cost對不同operation都一樣)

一: Stack 栗子 Stack的基本動作: Push(S,x) Pop(S) Multipop(S,k) while not STACK_EMPTY(S) and k>0 POP(S) k=k-1 使用平常的方法: 𝑇 𝑛 =𝑂 𝑛 2 𝑂(1) 𝑂(1) min 𝑠,𝑘 =𝑂(𝑛)

Aggregated Analysis 但是事實上,雖然單一Multipop operation要花很多時間 任何n個連續的operation最多只會花𝑂 𝑛 . 因為stack裡面最多只會放n個(n個push後) 而不管是pop或Multipop, 最多真正pop的數目也只會是n 因此總共花的時間不會超過𝑂 𝑛 . 𝑇 𝑛 =𝑂 𝑛 所以平均每個operation所花時間為 𝑂 𝑛 𝑛 =𝑂 1 在aggregated analysis裡面, 我們把每個operation的amortized cost設定為average cost. 在這個例子裡,也就說三種operation的amortized cost都是𝑂 1 .

二: 二進位計數器 栗子 A[0..k-1]放 二進位數的bits k位數 INCREMENT(A) i=0 while A[i]==1 and i<A.length A[i]=0 i=i+1 if i<A.length A[i]=1 n個operation要花多少時間? A[5] A[4] A[3] A[2] A[1] A[0] 1

使用平常的方法 執行一次INCREMENT最多花Θ 𝑘 最糟的狀況: 每一位都是1, 全部清成0 因此n次INCREMENT要花O 𝑛𝑘 正確的bound, 但是太鬆

Aggregated Analysis 翻 𝑛 4 次 第i位數翻 𝑛 2 𝑖 次 翻n次 Counter A[7] A[6] A[5] 翻 𝑛 4 次 第i位數翻 𝑛 2 𝑖 次 翻n次 Counter A[7] A[6] A[5] A[4] A[3] A[2] A[1] A[0] Cost 1 2 3 4 7 5 8 6 10 11 15 翻 𝑛 8 次 翻 𝑛 2 次

Aggregated Analysis 所以n個operation的cost應為: 𝑇 𝑛 = 𝑖=0 𝑘−1 𝑛 2 𝑖 <𝑛 𝑖=0 ∞ 1 2 𝑖 =2𝑛=𝑂 𝑛 Amortized cost for each operation: 𝑇 𝑛 𝑛 = 𝑂 𝑛 𝑛 =𝑂 1

The accounting method “發明”一種給每個operation不同”虛擬cost”的方法 (用這種方法可能分析T(n)比較容易) 每個operation給不一樣的amortized cost 每個operation的amortized cost可能比實際的cost少一點或多一點 可以把amortized cost > 實際cost想成是存錢 可以把amortized cost < 實際cost想成是花錢 有些operation可能多存一些錢, 供給後面的其他花錢的operation使用

限制 如果我們想要用amortized cost總和來分析T(n)最大有多少, 則必須滿足 i=1 n 𝑐 𝑖 ≥ i=1 n 𝑐 𝑖 注意上面的條件是”任何n個operation”都要符合喔! 如果不符合: 則不能保障”如果 i=1 n 𝑐 𝑖 是𝑂 𝑓 𝑛 則 i=1 n 𝑐 𝑖 也是𝑂 𝑓 𝑛 ” (也就是說, 不可以使某個operation多花的錢大於之前存的錢) 𝑐 𝑖 :amortized 花費 𝑐 𝑖 : 實際上的花費

一: Stack 假設我們設定以下的amortized cost: Push: 2 Pop: 0 Multipop: 0 注意multipop的amortized cost與actual cost是不同的 O(1) versus O(n) 這樣, push先存下的錢, 足夠讓pop和multipop花嗎? Pop&Multipop的amortized cost設成0, 因此會花先存下來的錢

存錢和花錢的故事 Push: 付兩塊錢 一塊錢付掉push本身花的時間 一塊錢先存起來 (跟著push進去stack的item) 1 2 也就是說, 不管n個operation的順序是怎麼樣, 永遠不會有情形是花錢花超過已經存下來的錢. 每個已經在stack裡面的item都已經預先存下了錢給pop or Multipop用. 2 1 存起來的錢, 是用來給之後pop出來的花的(不管是pop or Multipop) the total amortized cost is always a upper bound of the total actual cost.

Total Amortized Cost 然後呢? Total amortized cost=2×push operation數目=O(n) 因此total actual cost也是O(n)

二: 二進位計數器 假設我們這樣定義amortized cost: 設定一個bit為1的時候: 2 其他都是0 這樣的設計會不會有錢不夠花的狀況?

存錢和花錢的故事 Part II 設A[0]=1: 付兩塊錢 A[5] A[4] A[3] A[2] A[1] A[0] 一塊錢付掉設A[0]=1本身花的時間 一塊錢先存起來 (跟著A[0]的bit 1) A[0] A[5] A[4] A[3] A[2] A[1] A[0] 1 設A[0]=0: 不付錢 A[5] A[4] A[3] A[2] A[1] A[0] 1 用存起來的一塊錢付 A[1] 設A[1]=1: 付兩塊錢 也就是說, 不管n個operation的順序是怎麼樣,永遠不會有情形是花錢花超過已經存下來的錢.每個bit=1都已經預先存下了錢給set bit=0的時候用. 一塊錢付掉A[1]=1本身花的時間 一塊錢先存起來 (跟著A[1]的bit 1) the total amortized cost is always a upper bound of the total actual cost.

Total Amortized Cost Total amortized cost=n個INCREMENT設定bit=1的次數 因此n次最多設定n個bit為1 Total amortized cost=O(n) Total actual cost=O(n)

The potential method 比較: Accounting method是使用”先存後花”的方式 Potential method則是用potential來計算”之前的operation使目前的資料結構有殘存多少能量” 物理定義:Potential energy is the energy stored in a body or in a system due to its position in a force field or due to its configuration* *http://en.wikipedia.org/wiki/Potential_energy

定義 𝐷 𝑖 :做完第i個operation之後的data structure (一開始為 𝐷 0 ,結束n個operation後為 𝐷 𝑛 ) Φ( 𝐷 𝑖 ): D 𝑖 的potential (自己定義) 則第i個operation的amortized cost為 𝑐 𝑖 = 𝑐 𝑖 +Φ 𝐷 𝑖 −Φ 𝐷 𝑖−1 amortized cost=actual cost加上potential的改變 𝑖=1 𝑛 𝑐 𝑖 = 𝑖=1 𝑛 (𝑐 𝑖 +Φ 𝐷 𝑖 −Φ 𝐷 𝑖−1 ) = 𝑖=1 𝑛 𝑐 𝑖 +Φ 𝐷 𝑛 −Φ( 𝐷 0 )

限制 要怎麼確定total amortized cost是total actual cost的upper bound呢? 要確定: 𝑖=1 𝑛 𝑐 𝑖 ≥ 𝑖=1 𝑛 𝑐 𝑖 𝑖=1 𝑛 𝑐 𝑖 +Φ 𝐷 𝑛 −Φ 𝐷 0 ≥ 𝑖=1 𝑛 𝑐 𝑖 也就是Φ 𝐷 𝑛 ≥Φ 𝐷 0 通常不知道n是多少 所以也就是必須對於任何i Φ 𝐷 𝑖 ≥Φ 𝐷 0 通常會希望Φ 𝐷 0 =0, Φ 𝐷 𝑖 ≥0 𝑐 𝑖 :amortized 花費 𝑐 𝑖 : 實際上的花費 Φ( 𝐷 𝑖 ): D 𝑖 的potential

概念 𝑐 𝑖 = 𝑐 𝑖 +Φ 𝐷 𝑖 −Φ 𝐷 𝑖−1 amortized cost ≥ actual cost 𝑐 𝑖 = 𝑐 𝑖 +Φ 𝐷 𝑖 −Φ 𝐷 𝑖−1 amortized cost ≥ actual cost 則可以想成是存錢. (存到potential裡面去) Φ 𝐷 𝑖 −Φ 𝐷 𝑖−1 ≥0 amortized cost < actual cost 則可以想成是花錢. (從potential裡面拿出錢來) Φ 𝐷 𝑖 −Φ 𝐷 𝑖−1 <0

一: Stack 定義Φ: stack裡面有多少個item 則Φ 𝐷 0 =0 (一開始stack沒有東西) 且Φ 𝐷 𝑖 ≥Φ 𝐷 0 =0 total amortized cost是total actual cost的upper bound

Amortized costs 如果第i個operation是push, 目前stack有s個item 則Φ 𝐷 𝑖 −Φ 𝐷 𝑖−1 = 𝑠+1 −𝑠=1 𝑐 𝑖 = 𝑐 𝑖 +Φ 𝐷 𝑖 −Φ 𝐷 𝑖−1 =1+1=2 如果第i個operation是pop, 目前stack有s個item 則Φ 𝐷 𝑖 −Φ 𝐷 𝑖−1 = 𝑠−1 −𝑠=−1 𝑐 𝑖 = 𝑐 𝑖 +Φ 𝐷 𝑖 −Φ 𝐷 𝑖−1 =1−1=0 如果第i個operation是Multipop(S,k) , 目前stack有s個item (請同學練習看看) 設 𝑘 ′ = min 𝑘,𝑠 則Φ 𝐷 𝑖 −Φ 𝐷 𝑖−1 = 𝑠− 𝑘 ′ −𝑠=−𝑘′ 𝑐 𝑖 = 𝑐 𝑖 +Φ 𝐷 𝑖 −Φ 𝐷 𝑖−1 = k ′ − k ′ =0

Total actual cost 因為三個operation的amortized cost都是O(1) 因此n個operation (由三種operation組成)的amortized cost是O(n) Total amortized cost是total actual cost的upper bound 因此total actual cost也是O(n)

二: 二進位計數器 定義Φ: A[]裡面有幾個bit是1 假設 𝑏 𝑖 為做完第i個operation後A[]裡面bit是1的數目 假設第i個operation把 𝑡 𝑖 個bit從1設成0 則第i個operation的實際花費最多為 𝑡 𝑖 +1 ( 𝑡 𝑖 個10, 最多1個01) (想想什麼時候沒有01) 如果 𝑏 𝑖 =0, 則 𝑏 𝑖−1 = 𝑡 𝑖 如果 𝑏 𝑖 >0, 則 𝑏 𝑖 = 𝑏 𝑖−1 − 𝑡 𝑖 +1  𝑏 𝑖 ≤ 𝑏 𝑖−1 − 𝑡 𝑖 +1 Φ 𝐷 𝑖 −Φ 𝐷 𝑖−1 = 𝑏 𝑖 − 𝑏 𝑖−1 ≤1− 𝑡 𝑖

Amortized costs 𝑐 𝑖 = 𝑐 𝑖 +Φ 𝐷 𝑖 −Φ 𝐷 𝑖−1 ≤ 𝑡 𝑖 +1 + 1− 𝑡 𝑖 =2 Φ 𝐷 𝑖 −Φ 𝐷 𝑖−1 = 𝑏 𝑖 − 𝑏 𝑖−1 ≤1− 𝑡 𝑖 Amortized costs 𝑐 𝑖 = 𝑐 𝑖 +Φ 𝐷 𝑖 −Φ 𝐷 𝑖−1 ≤ 𝑡 𝑖 +1 + 1− 𝑡 𝑖 =2 如果一開始counter=0, 則 Φ(𝐷 𝑖 )≥Φ 𝐷 0 =0 (所有i) total amortized cost為total actual cost之upper bound n個INCREMENT之total amortized cost為O(n) 所以total actual cost也是O(n)

變形 如果一開始我們不從0開始count呢? 𝑏 0 ≠0, Φ 𝐷 𝑖 ≥Φ 𝐷 0 不一定成立, total amortized cost不一定是total actual cost的upper bound 使用原本的定義的話 𝑐 𝑖 = 𝑐 𝑖 +Φ 𝐷 𝑖 −Φ 𝐷 𝑖−1 ≤ 𝑡 𝑖 +1 + 1− 𝑡 𝑖 =2 𝑖=1 𝑛 𝑐 𝑖 = 𝑖=1 𝑛 𝑐 𝑖 −Φ 𝐷 𝑛 +Φ 𝐷 0 ≤2𝑛−Φ 𝐷 𝑛 +Φ 𝐷 0 =2𝑛− 𝑏 𝑛 + 𝑏 0 因為只有k位數, 0≤ 𝑏 0 , 𝑏 𝑛 ≤𝑘 所以當k=𝑂(𝑛)的時候 我們知道total actual cost =𝑂 𝑛 !

來一個實際一點的例子… 大家很不愛用malloc, realloc, delete 陣列一開始就開很大 浪費記憶體空間 Dynamic table: 怎麼隨時動態調整table大小, 使得不會有太多空間浪費, 平均起來也不會浪費很多時間? load-factor: 𝛼 𝑇 = 𝑇.𝑛𝑢𝑚 𝑇.𝑠𝑖𝑧𝑒 (跟hash table的定義一樣)

只有insert的case Table_Insert(T,x) if T.size==0 allocate T.table with 1 slot T.size=1 if T.num==T.size allocate new-table with 2*T.size slots insert all items in T.table into new-table free T.table T.table=new-table T.size=2*T.size insert x into T.table T.num=T.num+1 這邊insert了T.size次 假設主要花費時間是這些insertion 這邊insert了1次

原本的方法 (非amortized analysis) 𝑐 𝑖 =? 如果原本的table還有空間, 則 𝑐 𝑖 =1 如果原本的table沒有空間, 則 𝑐 𝑖 =𝑖 (1個新的insertion跟i-1個搬移insert到新的table) 所以一個operation的cost為𝑂(𝑛) n個operation的cost為𝑂 𝑛 2 一樣; 正確但是不tight

Aggregate analysis 𝑐 𝑖 = 𝑖 1 𝑐 𝑖 = 𝑖 1 𝑖=1 𝑛 𝑐 𝑖 ≤n+ 𝑗=0 log 𝑛 2 𝑗 =𝑛+ 2 log 𝑛 +1 ≤𝑛+2𝑛=3𝑛 所以n個operation的cost=3n=O(n) 平均每個operation的cost=3=O(1) , if i-1 is an exact power of 2 otherwise

Accounting method 我們設計每個table-insert的amortized cost是3 insert的時候付3塊錢 size/2 一塊錢把最新的item insert到table的時候花掉 一塊錢給之前已經在裡面的其中一個item (準備當之後滿了需要移動的時候可以花掉) 一塊錢給自己 (準備當之後滿了需要移動的時候可以花掉) 當全滿的時候, 則每一個item都有預存了一塊錢可以拿來搬移(insert到新的table)

Potential method 定義Φ 𝑇 =2𝑇.𝑛𝑢𝑚−𝑇.𝑠𝑖𝑧𝑒 則Table-insert沒有造成把table變大的時候: 𝑐 𝑖 = 𝑐 𝑖 +Φ 𝐷 𝑖 −Φ 𝐷 𝑖−1 =1+ 2𝑛𝑢 𝑚 𝑖 −𝑠𝑖𝑧 𝑒 𝑖 2𝑛𝑢 𝑚 𝑖 −𝑠𝑖𝑧 𝑒 𝑖 − 2𝑛𝑢 𝑚 𝑖−1 −𝑠𝑖𝑧 𝑒 𝑖−1 =1+ 2𝑛𝑢 𝑚 𝑖 −𝑠𝑖𝑧 𝑒 𝑖 2𝑛𝑢 𝑚 𝑖 −𝑠𝑖𝑧 𝑒 𝑖 − 2 𝑛𝑢 𝑚 𝑖 −1 −𝑠𝑖𝑧 𝑒 𝑖 =3 當Table-insert造成把table變大的時候: 𝑐 𝑖 = 𝑐 𝑖 +Φ 𝐷 𝑖 −Φ 𝐷 𝑖−1 =𝑛𝑢 𝑚 𝑖 + 2𝑛𝑢 𝑚 𝑖 −𝑠𝑖𝑧 𝑒 𝑖 − 2𝑛𝑢 𝑚 𝑖−1 −𝑠𝑖𝑧 𝑒 𝑖−1 =𝑛𝑢 𝑚 𝑖 + 2𝑛𝑢 𝑚 𝑖 −2 𝑛𝑢 𝑚 𝑖 −1 − 2 𝑛𝑢 𝑚 𝑖 −1 − 𝑛𝑢 𝑚 𝑖 −1 2 𝑛𝑢 𝑚 𝑖 −1 − 𝑛𝑢 𝑚 𝑖 −1 =3

Reading assignment Section 17.4.2 可以長大也可以縮小的dynamic table 作業會有17.4-2 (延續你的閱讀的題目)