Амортизированное время. Алгоритмы и структуры данных

1.

Амортизированное время
Алгоритмы и структуры данных
УрФУ, ФИИТ

2.

Время работы структур данных
время работы операций в структурах данных:
• время работы в худшем случае
• ожидаемое время работы
• амортизированное время работы
на примере List / std::vector / ArrayList в C# / C++ / Java
class DynamicArray {
Add(float x);
// добавить x в конец массива
ReduceSize(int newSize); // уменьшить размер массива
float ElementAt(int i); // i-й элемент массива
}

3.

Динамический массив
Add(float x) {
if (size == capacity) {
const a = 2;
// возможны варианты: 3/2, 8/5
capacity = size * a;
tmp = new float[capacity];
Copy(buffer, tmp, size);
// копировать buffer в начало tmp
buffer = tmp;
}
buffer[size] = x;
size++;
}
ReduceSize(int newSize) { size = min(size, newSize); }
float ElementAt(int i) { return buffer[i]; }

4.

Динамический массив
• ElementAt и ReduceSize работают за