Explore
For Enterprise
Join for Free
Log In

University of Pennsylvania
Earn an Ivy League CS Master’s designed for non-CS majors
Applications for Penn’s online Master of Computer and Information Technology degree are now open.
University of North Texas
Easily transfer credits to earn your bachelor’s degree faster
Earn your bachelor’s degree online from UNT, a top 9 research school in Texas.

浏览 Coursera 的全部课程

浏览
顶级课程
企业版
登录
免费加入

Amortized Analysis: Summary

Loading...

数据结构

加州大学圣地亚哥分校

4.7（2,467 个评分） | 100K 名学生已注册

课程 2（共 6 门，数据结构与算法专项课程）

A good algorithm usually comes together with a set of good data structures that allow the algorithm to manipulate the data efficiently. In this course, we consider the common data structures that are used in various computational problems. You will learn how these data structures are implemented in different programming languages and will practice implementing them in our programming assignments. This will help you to understand what is going on inside a particular built-in implementation of a data structure and what to expect from it. You will also learn typical use cases for these data structures. A few examples of questions that we are going to cover in this class are the following: 1. What is a good strategy of resizing a dynamic array? 2. How priority queues are implemented in C++, Java, and Python? 3. How to implement a hash table so that the amortized running time of all operations is O(1) on average? 4. What are good strategies to keep a binary tree balanced? You will also learn how services like Dropbox manage to upload some large files instantly and to save a lot of storage space! Do you have technical problems? Write to us: coursera@hse.ru

查看授课大纲

您将学习的技能

Binary Search Tree, Priority Queue, Hash Table, Stack (Abstract Data Type), List

审阅

4.7（2,467 个评分）

5 stars
1,819 ratings
4 stars
521 ratings
3 stars
88 ratings
2 stars
15 ratings
1 star
24 ratings

SG

Oct 28, 2019

I found the course a little tough, but it's worth the effort. It takes more time than mentioned. Apart from that, it is actually good and covers most of the topics required for interviews.

AS

Sep 19, 2019

The best data structures course that I have taken!\n\nThe complex topics are made simpler at the expense of teaching style that allowed me to make it applicable in a real world situations.

从本节课中

Dynamic Arrays and Amortized Analysis

In this module, we discuss Dynamic Arrays: a way of using arrays when it is unknown ahead-of-time how many elements will be needed. Here, we also discuss amortized analysis: a method of determining the amortized cost of an operation over a sequence of operations. Amortized analysis is very often used to analyse performance of algorithms when the straightforward analysis produces unsatisfactory results, but amortized analysis helps to show that the algorithm is actually efficient. It is used both for Dynamic Arrays analysis and will also be used in the end of this course to analyze Splay trees.

Dynamic Arrays8:33

Amortized Analysis: Aggregate Method5:43

Amortized Analysis: Banker's Method6:11

Amortized Analysis: Physicist's Method7:33

Amortized Analysis: Summary2:53

教学方

Alexander S. Kulikov
Visiting Professor
Michael Levin
Lecturer
Daniel M Kane
Assistant Professor
Neil Rhodes
Adjunct Faculty

以免费的价格试听课程

脚本

Let's go back to the dynamic array. So are there alternatives to doubling the array size? Right, we doubled each time. What happens if we didn't double? Well we could use some different growth factor. So for instance, we could use 2.5. So grow the array by more than two, or grow the array by less than two. As long as we used some constant multiplicative factor, we'd be fine. The question is can we use a constant amount? Can we add by a particular amount, like, let's say, 10 each time? And the answer is really, no. And the reason is, as the array got bigger and bigger, and we have to resize every ten times, we just don't have enough time to accumulate work in order to actually do the movement. Let's look at another way. Let's look at an aggregate method. Let's say c sub i is the cost of the i'th insertion. We're going to define that as one, for putting in the i'th element, plus either i-1 if the i-1'th insertion makes the dynamic array full. So that is if i-1 is a multiple of 10 and it's 0 otherwise. By the definition of aggregate method which is just the sum of the total costs divided by n and that's n plus again that's the one summed n times is just n plus the summation from one to (n-1)/10 of 10j. That is just the multiples of 10. All the way up to but not including n. So 10, 20, 30, 40 and so on. All that divided by n. Well, we can pull the 10 out of that summation so it's just 10 x the summation j = 1 to (n- 1)/10 of j. So that's just numbers 1, 2, 3, 4, and so on, all the way up to (n- 1)/10. That is O(n squared). That summation. So we've got n+10 times O(N^2)/n=O(n^2)/n=O(n). So this shows that if we use a constant amount to grow the dynamic array each time that we end up with an amortized cost for push back of O(n) rather than O(1). So it's extremely important to use a constant factor. So in summary we can calculate the amortized cost in the context of a sequence of operations. Rather than looking at a single operation in its worst case we look at a totality of a sequence of operations. We have three ways to do the analysis. The aggregate method, where we just do the brute-force sum based on the definition of the amortized cost. We can use the banker's method where we actually use tokens and we're saving them conceptually in the data structure. Or the physicist's method where we define a potential function, and look at the change in that potential. Nothing changes in the code. We're only doing runtime analysis, so the code doesn't actually store any tokens at all. That's an important thing to remember. That is dynamic arrays and amortized analysis.

探索我们的目录

免费加入并获得个性化推荐、更新和优惠。

Coursera

关于
管理团队
工作机会
目录
证书
MasterTrack™ 证书
学位
企业版
政府版
面向校园

社区

学生
合作伙伴
开发者
Beta 测试人员
专业译员
博客
技术博客

更多

条款
隐私
帮助
内容访问
媒体
联系我们
目录
附属公司

随时随地学习

关注我们

© 2020 Coursera Inc.保留所有权利。