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

1.

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

2.

Алгоритм
void Sort(int[] array)
{...}
вход
выход
bool BinarySearch(
int[] sortedArray, int element)
{...}

3.

Структуры данных
модификация
запрос
class Stack {
Push(double element);
double Pop();
}
class DynamicArray {
Add(double element);
RemoveAt(int index);
double ElementAt(int index);
}

4.

Алгоритм ≈ программа
• Главные задачи — оптимизировать что-то:
• время работы
• используемую память
• использование внешних носителей / сети
• использование кеша
• возможности для распараллеливания
• Нужно как-то измерять время
• Практически, на реальном компьютере?
• Теоретически, на модели компьютера!

5.

RAM модель
Random Access Machine (RAM)
• Алгоритм — программа на языке С
• Ввод может быть произвольно большой длины
• Элементарные операторы выполняются за единицу времени
• Можно выделять массивы произвольной длины
• Чтение/запись элемента массива выполняется за единицу времени
(random access memory, RAM)
• Индексы массивов (числа от 0 до