[ACE] Amortized analysis

Amortized analysis

Why talking about amortized analysis

When we are learning “Vector” in ACE class, we came up with a growable array-based vector.
We want to know what if we execute “push” operation, but the array is full. Instead of throwing a exception, we would like to replace the array with a larger one
Algorithm push(o)
    if t = s.length -1
then 
    A <- new array of size ...
    for i <- 0 to t do
    A[i] <- S[i]
    t <- t+1
    A[t+1] <- o
    garbage collection S
From pseudo-code above, what should be the size of the new array?
There are two simple strategy you can came up with quickly
• incremental strategy: increase size by a constant c
• doubling strategy: double the size

What is the common analysis for this question?

Suppose some individual operation (such as ‘push’) takes time T in the worst-case.
So for the total s operations, the worst-case time should be sT(upper bound)
• however, such an upper-bound might not ever occur. Because there will never be always worst case
Suppose do a sequence of operations, and there are s such operations taking time Ts
The time Ts might well be o(sT) even in the worst-case(little-o)

So what is the cost for each operation in this case(if we apply doubling strategy)?

we do every insert operation step by step like the image.
Do it step by step
we can draw a table regarding the insert sequence i, the size of array size(i) and the cost of ith insert C(i)
Note that C(i) = i, if i-1 is the power of 2
or C(i) = 1 ,otherwise
enter image description here
If we add all the C(i) together, we can get the cost of n inserts, and each C(i) can be 1 or 1 add a number which is 2 to the power of something.
enter image description here
From the analysis, we found it will be less than 3n which is O(n), so each operations takes O(1) time.
It is amortized analysis, which is not simply times the worst case with operation number but analyze in detail

So what is the official definition?

Sequence!!

Amortized analysis is a technique for analyzing an algorithm’s running time. It is often appropriate when one is interested in understanding asymptotic behavior over sequences of operations.

Methods

There are generally three methods for performing amortized analysis: the aggregate method, the accounting method, and the potential method. All of these give the same answers, and their usage difference is primarily circumstantial and due to individual preference. In CLRS, it introduce three method but in class we just cover aggregate method.

Why is amortised analysis different from the average case analysis?

• (long) real sequence of dependent operations
• vs.
• Set of (possibly independent) operations
Because when analyze amortized analysis, we consider the relationship and impact between operation.

Incremental Strategy Analysis

We have cover the doubling strategy analysis, now we finish the incremental strategy analysis.
• Take c=3, with start capacity of 3, then a sequence of pushes might have costs for each push as follows:
1,1,1,3+1,1,1,6+1,1,1,9+1,1,1,12+1,1,1, 15+1,1,1,18+1,…
enter image description here

Is it says doubling are better than incremental?

Not really, though doubling has lower amortized complexity, it might need more space. The space will be waste and might not be use.

评论

发表评论

此博客中的热门博文

[MLE] W2 Multivariate linear regression

图片
Multivariate linear regression What we have talked about in week 1 is linear regression with single feature. For example, in the house pricing predicting problem, we only use the size of house (x) to predict the price (y) . But what if there are other features like age, bedroom numbers and so on? Linear regression with multiple variables is also known as “multivariate linear regression” According to the graph above, we now have new representation symbols: n = number of features m = number of training examples \(x^{(i)}\) = \(i^{th}\) training example \(x^{(i)}_j\) = feature j in \(i^{th}\) training example 1416 is \(x_{1}^{(2)}\) in this case, m is 47 for example, n is 4. Hypothesis function The multivariable form of the hypothesis function accommodating these multiple features is as follows: if we make \(x_0\) to 1, the \(h_{\theta}(x)\) will be \(\theta^Tx\), which is \(\theta\) transpose matrix multiply by x, where \(\theta\) is a vector of 1 by(n+1) dimension an
阅读全文

[MLE] W1 Introduction

图片
Before get started The blog is based on the machine learning course on Coursera, taught by Andrew Ng . From today, i will begin my study trip on Machine learning, which will be labelled as MLE. This course will last 11 weeks and today is week 1. The application of machine learning is everywhere: Database mining Applications can’t program by hand Self-customizing program Understanding human learning(brain, real AI) Introduction What is Machine Learning Two definitions of machine learning are offered: Arthur Samuel described it as: “the field of study that gives computers the ability to learn without being explicitly programmed.” This is an older, informal definition. Tom Mitchell provides a more modern definition: “A computer program is said to learn from experience E with respect to some class of tasks T and performance measure P, if its performance at tasks in T, as measured by P, improves with experience E.” If we raise a example of what is machine learning: If
阅读全文

[AIM] MetaHeuristics

图片
Day2 Outline Metaheuristics -definition Single point based search method(simple stochastic local search) Iterated local search Scheduling Tabu Search Metaheuristic what is a metaheuristic? A metaheuristic is a high-level problem independent algorithmic framework that provides a set of guidelines or strategies to develop heuristic optimization algorithms. what is the difference between heuristic and metaheuristic? Heuristic : Heuristics are problem-dependent techniques. As such, they usually are adapted to the problem at hand and they try to take full advantage of the particularities of this problem. However, because they are often too greedy, they usually get trapped in a local optimum and thus fail, in general, to obtain the global optimum solution. Metaheuristic : Meta-heuristics, on the other hand, are problem-independent techniques . As such, they do not take advantage of any specificity of the problem and, therefore, can be used as black boxes . In general, t
阅读全文