[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] Linear Classification

图片
Linear Classification Discriminant functions Least squares for classification Fisher’s linear discriminant K-Nearest Neighbour(KNN) Classification What’s decision boundaries/linearly separable? The goal in classification is to take an input vector x and to assign it to one of K discrete classes \(C_k\) where k = 1,…,K. In the most common scenario, the classes are taken to be disjoint, so that each input is assigned to one and only one class. The input space is thereby divided into decision regions whose boundaries are called decision boundaries or decision surfaces. In this blog, we consider linear models for classification , by which we mean that the decision surfaces are linear functions of the input vector x and hence are defined by (D-1) -dimensional hyperplanes within the D-dimensional input space. For example: in 3D input space, the decision boundary will be a 2D surface What is Linear Separability Linearly separable data: Datasets whose classes can be separated by
阅读全文

[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
阅读全文

[CS231] Neural Networks

图片
Neural Network Table of Contents: Quick intro without brain analogies Modeling one neuron Biological motivation and connections Single neuron as a linear classifier Commonly used activation functions Neural Network architectures Layer-wise organization Summary Additional references Quick intro It is possible to introduce neural networks without appealing to brain analogies. In the section on linear classification we computed scores for different visual categories given the image using the formula \( s = W x \), where \(W\) was a matrix and \(x\) was an input column vector containing all pixel data of the image. In the case of CIFAR-10, \(x\) is a [3072x1] column vector, and \(W\) is a [10x3072] matrix, so that the output scores is a vector of 10 class scores. An example neural network would instead compute \( s = W_2 \max(0, W_1 x) \). Here, \(W_1\) could be, for example, a [100x3072] matrix transforming the image into a 100-dimensional intermediate vector. The funct
阅读全文